最长递增子序列之动态规划解法
最近在leetcode 做了这样一道动态规划的题目，看了答案以后发现并不是非常的困难，但是也困扰了我好久（属实垃圾。。）。过了几天以后再次看这道题，虽说有了一定思路，但是依然没有解决出来（垃圾实锤），特此记录一下这道题的解决过程，应用一下前文所述的框架。
先看题目：
题目描述本身并没有什么坑点，也算是一道很典型的动态规划问题（子序列+最大值）。
1. 确定问题的状态和dp数组
首先由于这道题目只是求自身的最长递增子序列，并没有设计到和其他序列进行比较，所以暂时可以确定dp数组是一个一维数组。在这个问题中，没有特别明显的状态，不太方便从这个角度分析。接下来就是考虑dp数据的含义了，既然是一维数组，那么最直接的想法就是dp[i]就表示从nums[0…i]的最大长度（不是说一定从0开始），因为最终的答案肯定是在dp数组中，再结合题目，很容易得出这个定义。带入尝试一下发现没有问题，继续分析。
2. 确定当前的选择
我们假设这样一种情况：现在我们通过某种方式已经求出了dp[i-1]的值，现在我们想要求dp[i]的值。面对这样的情况，我们可以有哪几种选择或者说操作呢？
首先，求出了dp[i-1]就说明nums[0…i-1]中的最长长度以及有了。现在我们遍历到了nums[i]的位置，那么最直接的想法就是判断是否将nums[i]接到前面的最长序列上。又由于子序列不一定是连续的（即dp[i-1]和dp[i-2]的情况可能不一样），所以到底接在哪个最大子序列上也是一个选择。综合起来，选择就是是否将nums[i]接在nums[0…i-1]中的最长子序列中以及接在哪个一最长子序列中。
3. 写出状态转移方程
明确了dp数组的含义和选择，再结合数学归纳法分析一下，很容易得出该问题的状态转移方程：
dp[i] = max(dp[j]+1, dp[i]) for j in range(i)4. 初始话base case
本题的base case很好得出，子序列最少也需要包含自己，所以base case就是1。由于dp数组为一维，每次求dp[i] 都需要 dp[0…i]，故按照正序遍历即可解决问题。
小结
到此，这个问题已经圆满解决了，但是还是有一些小瑕疵：对于dp数组的定义。在本问题中，将dp数组定义为nums[0…i]的最长子序列长度其实并不太合适，但是这样定义又是我自己的第一反应，这也是我在第二次解题时仍然遇到困难的主要原因。事后我在查看题解时发现了一种更加合理的定义方式：dp[i]的含义时以nums[i] 结尾的最长子序列长度。由于这个定义明确了每个最长子序列的末尾，很巧妙的契合了我们的“选择”，即到底接在哪个最长子序列的末尾，那么解决接下来的问题就势如破竹了。
从这里也可以看出dp数组的定义真的对于动态规划问题的解决十分的关键。可以说一个好的dp数组的定义是解决动态规划问题的关键所在。dp数组定义的好，推导状态转移方程也是水到渠成的事情。但是这种在我看来比较巧妙地dp数组的定义方式，只能靠不断积累（智商有限）。
下面附上完整代码：
def lengthOfLIS(nums) ->int:
n = len(nums)
if n == 0:
return 0
dp = [1] * n # 初始化
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[j]+1, dp[i])
return max(dp)
