我正在解决这个问题:https://www.interviewbit.com/problems/double-increasing-series/
基本上问题是:
给定两个整数A和B。求长度为B的序列的个数，使得该序列的每个元素都是正整数且小于等于A，并且序列中每个前一个元素都小于或等于下一个元素的一半。
这是一个动态规划问题。其现场解为:DP (i, j) = DP (i-1, j) + DP (floor(i/2), j-1).
谁能解释一下这个结果是怎么来的?我上网搜索了，但找不到任何解释。
公式为DP[i][j] = DP[i-1][j] + DP[i/2][j-1]，其中
i为序列的最大值(当然是序列的最后值)。j为序列长度。DP[i][j]为以整数<= i结尾、长度为j的序列总数。
现在试着通过一个例子来理解这个公式。
假设您想要找到以整数<= 50结尾且长度为5的序列的数量，表示DP[50][5]。现在考虑一下，以整数<= 49结尾，长度为5 (DP[49][5])的序列也可以计数为以整数<= 50结尾，长度为5 (DP[50][5])的序列。
现在我们将考虑那些严格以整数50结束的序列。现在，以整数<= 25(50 / 2)结尾，长度为4 (5 - 1)的序列表示DP[25][4]。通过在这些序列的末尾加上50，我们可以得到以50结尾、长度为5的新序列。所以把DP[49][5]和DP[25][4]相加，就得到DP[50][5]。