初级里面的代码我跑了一下，
如果我的初始序列为5, 3, 4, 2, 8, 6, 7 那么对应的d是1, 1, 2, 1, 3, 3, 4 也就是说5, 3, 4, 2的最长子序列是1，虽然最后的最大长度是对的，但是中间结果明显不对。这样的话，这个状态转移方程d(i) = max{1, d(j)+1},其中j<i,a[j]<=a[i]也就有问题了。 如果是我理解有误还请博主指正。="">

又读了几遍，是我的错，d[i]表示前i个数中以A[i]结尾的最长非降子序列的长度

高级篇里，楼主的解释没太看懂，不太明白x1[y]到底表示的什么意思。不过自己有个思路不知道行不行，这个高级篇感觉就像是中级篇里来了两次，第一次按照中级篇那么走，找出一条能获得最多苹果的路径，然后把走过的更新成0。第二次走的时候，还是一样的找能找到最多苹果的路径（还是这个状态转移方程S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)）。不知道这样行不行。。。大家看看吧，有什么问题么？

不能这样想吧。因为你上一条路径走过的结果，会对下一条路径有影响。第二次走的最优解+第一次走的最优解，不一定就是整体的最优解。
比如下边的矩阵
0 3 1 0
2 2 2 0
第一次如果选最优的结果，就是7（0-3-2-2-0），那么第二次只能得到2（0-2-0-0-0），总数是9。如果第一次走的结果是6（0-3-1-2-0），第二次就可以走4（0-2-2-0-0），总数是10。
最后说下对作者做法的理解吧。可以看作甲乙丙三个人一起走，从左上到右下，m*n的矩阵，一行一行走，第一行会有C（n，3）个结果（假设一开始和最后，每个人都不会站在同一个格子上），即每个人各站一个格子，并且甲在乙之前，乙在丙之前，那么每一种结果都会对应一个总的苹果数量。同样，往下走一行，也是有C（n，3）个结果，要求同上，并且每一个结果可以通过上一行的结果来表示，这样就可以找到状态以及转移函数了。状态就是每一行三个人的位置以及对应的苹果总数，转移函数就是从上一行三个人的位置到当前行三个人的位置的走法（每个人的第一步必须往下走）以及可以得到的苹果数。
比如对于上边的矩阵，，第一行时，有4种结果，其中一种是（数字是位置下标） 甲0 乙1 丙 2，此时有4个苹果，到下一行，状态为 甲0 乙1 丙2，到这个状态只有一种走法，甲（下），乙（下），丙（下），这个走法获得6个苹果，所以该状态对应的结果是4+6=10。
说的有点繁琐，不知道能不能理解。

高级篇那个没看懂……

感觉可以将“中级”代码跑三次，只不过需要将每次最优路线上的苹果数量要改成0，这样做好理解些。。

dp每一步依赖于前面的变化，但是当前步骤不能改变将来的状态，不管你前面做了什么选择，剩下的步骤不过是结决一个同样条件、规模更小的子问题，但是如果你简单把问题简单拆成跑三遍，第一遍跑完，棋盘上的条件改变了，不能直接得到全局最优，除非能证明贪心算法

谢谢 Hawstein！之前一直没懂动态规划，刚看完初级部分终于明白动态规划的核心在于「拆解」和「状态转移」。
我不太会C++，于是将最长非降子序列用 Python 实现了一遍 https://gist.github.com/Vay... ，获益匪浅

高级中从上一行移动到下一行，上一行得到最优解能保证下一行也能得到最优解吗

我也有此疑问？好想不能确保最后得到的是最优解吧

为什么“我们要得到最优解， 路径之间不能相交”？

相交表示走重复路径，要得到最优解，当然走不同路径更好啊

高级苹果那题的有答案代码吗？看不太懂啊。“三条路径对应的x坐标要满足：x1[y] < x2[y] < x3[y]”，这句是什么意思？x1[y] < x2[y] < x3[y] ，指的是x坐标，还是（y,x1）里的苹果数？

指的是在y行的时候，坐标x1 < 坐标x2 < 坐标x3

高一初学OIer超级感谢！ 完美解答学算法的问题！ 以后我就是大师的脑残粉了

根据原文：d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;

如果有硬币2、4、7 ，当要凑3元时，按照该公式：d(0)=0; d(1)=0; d(2)=1;d(3)=d(3-2)+1 = 1;
但是实际上3是凑不出来的。
那这个公式是不是就存在问题了？

2.4.7的话，转移方程就不是d(i)=min{d(i-vj)+1}了

不对，转移方程还是这个，向楼上所说，对于非0子状态d(i)=0就是不合法的意思了（返回false），所以d(1)是不合法的，d(3)由d(1)得到，也是不合法的

即使如此也不影响，只要给d(3)一个合适的值，如False之类的，然后在求解如d(7-4)的时候，遇到false，跳过就是了。

以上代码我运行了下， 返回 4。这应该是错误的反回值。 输入为｛5,3,4,8,6,7｝
我分析了下你的算法。当i ＝ 4， A[i] ＝ 6 的时候，d[i] = 1, 但是 j 从0 － 3 循环执行的时候， A[0] = 5, d[0] = 1, 满足条件 if(A[j]<=A[i] && d[j]+1>d[i])Johnbenitez

thanks your translate

不好意思，这边我以为是连续的，其实是非连续的。这下我明白了。

你好， 在 dp 初级教程中
for(int i=0; i<n; ++i){="" d[i]="1;" for(int="" j="0;" j<i;="" ++j)="" if(a[j]<="A[i]" &&="" d[j]+1="">d[i])
d[i] = d[j] + 1;
if(d[i]>len) len = d[i];
}
以上代码我运行了下， 返回 4。这应该是错误的反回值。 输入为｛5,3,4,8,6,7｝
我分析了下你的算法。当i ＝ 4， A[i] ＝ 6 的时候，d[i] = 1, 但是 j 从0 － 3 循环执行的时候， A[0] = 5, d[0] = 1, 满足条件 if(A[j]<=A[i] && d[j]+1>d[i])
所以这个时候d[4] = 2; 但是这应该是不成立的。

我是个初学者，可能我理解有问题，还请帮忙看下。