Dynamic Programming

一维状态转移函数分以下两种情况：

• dp[i] 表示以第 i 个数组结尾的最大/小情况。一定是包含当前第 i 个数组的情况。而求解 dp[i] 往往需要向前遍历查找符合情况的 dp 数组，数组长度一般为 n，最后的结果是遍历 dp 数组，取数组的最大/小值。例如，121. 买卖股票的最佳时机。

• dp[i] 表示前 i 个数组的最大/小情况。不一定是包含当前第 i 个数组的情况。数组长度一般为 n + 1，最后的结果一定是 dp[n]。例如，122. 买卖股票的最佳时机 II.md。