思路：大部分人第一反应就是晕，正常算法解决不了考虑中间态，看看能不能有规律   ·设D[i]为走到第i层走法的

思路：考虑中间状态   ·设D[i][j]为棋盘位置(i,j)时，可以获得的最大价值;val[i][j]为（i

正确答案是C动态规划，利用问题的最优子结构性质，以自底向上的方式递归的从子问题的最优解逐步构造出整个问题的最优解。对于重叠子问题，一个典型的问题是求斐波那契数列的第N项.如果用递归的方法做会存在大量的重叠子问题，而利用动态规划的方法就是解决了重叠子问题。建立表格不断填表，相当于备忘录，也就是解决重叠子问题的技巧，典型的问题是斐波那契数列、背包问题等，许多动态规划问题都是定义数组，进行递推过程填充数组（模拟备忘录）。马尔科夫性，是随机过程中某事件的发生只取决于它的上一事件、是“无记忆”过程。而动态规划具有“记忆性”。