关于动态规划【力扣300.最长递增子序列的思考】

1、有问题的时候，打印dp数组，看一下问题在哪里。

（打印数组代码，如下图所示）

（解答错误，如下图所示）

上面两个【解答错误】说明：初始化没问题，但是dp数组里的值没有更新。

说明递推关系有问题，没有正确计算dp数组的值。

（定位问题，如下图所示）

（解决问题，修改代码，如下图所示）

2、dp数组的定义很重要

问题一：怎么在阅读题目的时候，确定dp数组的含义？

问题二：dp数组是用一维还是二维？

问题三：dp数组是用一维的一个变量还是两个？

回答上述三个问题的第一个问题：看题目的问题是什么，这题是要找到一个东西的长度。那么就让dp数组的含义为【最长递增子序列的长度为dp[]】。

回答上述三个问题的第二个问题：比如：0-1背包问题是如果选了一个物品，状态改变的对象有物品和书包两个。物品的状态由没被选变成了被选，书包的状态由没加这个物品的重量变成了加了这个物品的重量。本题在找最长递增子序列的时候，只会影响一个对象：最长子序列的长度。遍历到了下一个新的位置，最长子序列的长度又有可能变了，但是变的对象只有这一个。所以dp数组选用一维的。

回答上述三个问题的第三个问题：本题用了dp[i]和dp[j]，用了两个变量i和j。首先，由第二个问题的回答(遍历到了下一个新的位置，最长子序列的长度又有可能变了)可知，每移动到下一个位置，最长子序列的长度就有可能会变。所以dp[i]表示数组下标从0到i，截止位置i的最长子序列长度为dp[i]。但是因为i每往后移动一位，都会引进一个新的数字，这个数字可能会对最长子序列长度的计算有影响，所以要用第二个变量j来表示这个影响。用dp[i]表示当前最长子序列的长度，j遍历数组下标从0到i，dp[j]表示在当前截止位置i之前已经统计过的到截止位置j的最长子序列的长度。在前面统计过的dp[j]基础上计算dp[i]。所以要用两个变量。