Leetcode 300. 最长上升子序列
这道题并不是要求连续的，只要后面的数比前面的大，那么就是可以被添加到连续上升子序列中的，只是说每次应该加入较小的数字，才能给后面腾出更多的位置，道理是这么说的。
默认开始的状态一定是 1 因为就算是全部递减的值，它的最长上升子序列至少还是等于 1，也就是它本身。
DP [i]=Max (DP [i],DP [j-1]+1) 如果 $nums [i-1]<$nums [$j], 说明此时 $nums [i] 也能加入到子序列中
这个状态转移方程是什么意思呢？可以先看代码在进行解释。
/** * @param Integer[] $nums * @return Integer */ function lengthOfLIS($nums) { $size = count($nums); if ($size < 2) return $size; $dp[0] = $res = 1; for ($i = 1; $i < count($nums); $i++) { $dp[$i] = 1; for ($j = 0; $j < $i; $j++) { if ($nums[$j] < $nums[$i]) { $dp[$i] = max($dp[$i], $dp[$j] + 1); } } $res = max($res, $dp[$i]); } return $res; }
两层遍历，第一层表示的到第 i 个元素，整体的意思是，每次到第 i 个元素的时候，就去看 i 之前的已经推导出来的状态。j 的值就是 0 到 i, 只要 $nums[$j] < $nums[$i] 说明 i 的位置可以利用之前推导的结果组成一个最长上升的子序列。所以就把之前推导出的 $dp[$j] +1，和已经推导出的 $dp[$i] 进行比较，获取最大值，重新存储在 $dp[i] 中。然后每次全局更新最大上升子序列值，最后返回即可。
Leetcode 121. 买卖股票的最佳时机
这系列的题目很有意思，这道题只能有一次交易，就是求利益最大化的买卖。对于这里的状态定义，可能一开始难以想到，我们可以这样想，每一天我们的状态只会有三种，未持有股票 (没购买过)，持有股票以及未持有股票 (抛售了):
初始状态 $dp[0][0]=$dp[0][2]=0，$dp[0][1]= -第一天的价格。什么意思呢，其实就是初始状态的定义表示第一天没买股票，那么收益的值 0，即 $dp[0][0]=0，$dp[0][2] 表示第一天卖出股票的收益，因为第一天不存在卖，所以初始值也是 0。最后看 $dp[0][1]= -第一天的价格，这里表示如果第一天买了股票那么收益当然是负数的，即购买的价格。
状态定义完了，接下来就是状态转移方程了。也就是 $dp[i][0]，$dp[i][1] 以及 $dp[i][2] 咋么转移，我们可以这么想第 i 天持有未购买的情况只能是前面的也没购买，第 i 天持有的情况分为两种情况，一种是前一天已经持有了或者是前一天也是未持有状态然后今天购买持有了。剩下的第 i 天已出售情况只能是前一天持有的状态然后今天抛售了。这个理清楚了，代码也就好写了。
/** * @param Integer[] $prices * @return Integer */ function maxProfit($prices) { $dp[0][0] = $dp[0][2] = 0; $dp[0][1] = -$prices[0]; $res = 0; for ($i = 1; $i < count($prices); $i++) { $dp[$i][0] = $dp[$i - 1][0]; $dp[$i][1] = max($dp[$i - 1][1], $dp[$i - 1][0] - $prices[$i]); $dp[$i][2] = $dp[$i - 1][1] + $prices[$i]; $res = max($res, $dp[$i][0], $dp[$i][1], $dp[$i][2]); } return $res; }
Leetcode 122. 买卖股票的最佳时机 II
这是上一题的扩展，上一题只能交易一次，这一题可以多次交易。这道题我不用三个维护状态维护了，只有两种状态，第 i 天 未持有股票 和第 i 天持有股票。转移方程嘛就很好理解了，持有股票最大值，之前持有的最大值和之前不持有股票今天买了，取最大值。至于不持有股票最大值也分为两种，之前就一直不持有股票值和之前持有股票值今天卖了，取最大值，最后取 dp 数组中不持有股票最后的值。因为每一次更新的都是到 i 天的交易最大值，所以最后得到的必然是全局最大值。
/** * @param Integer[] $prices * @return Integer */ function maxProfit($prices) { if (count($prices) == 0) return 0; $dp[0][1] = -$prices[0]; $dp[0][0] = 0; for ($i = 1; $i < count($prices); $i++) { $dp[$i][1] = max($dp[$i - 1][1], $dp[$i - 1][0] - $prices[$i]); $dp[$i][0] = max($dp[$i - 1][1] + $prices[$i], $dp[$i - 1][0]); } return $dp[count($prices) - 1][0]; }
Leetcode 123. 买卖股票的最佳时机 III 终极难题
这道题又是上一版的扩展，因为规定了具体的交易次数，所以这一题单单是二维数据也必然不够了，因为我们还需要一个维度用来维护第 k 次交易的状态。这道题难度确实挺大的。
DP [i][k][j] 定义了一个三维数组，i 表示第几天 k 表示第几次交易 j 表示是否持有股票
然后分情况，第 i 天第 k 次都用两种情况持有股票和没有持有股票这两种状态。自己看代码理解一下吧。
/** * @param Integer[] $prices * @return Integer */ function maxProfit($prices) { $res = 0; $dp[0][0][0] = 0; $dp[0][0][1] = -$prices[0]; $dp[0][1][0] = -$prices[0]; $dp[0][1][1] = -$prices[0]; $dp[0][2][0] = 0; for ($i = 1; $i < count($prices); $i++) { $dp[$i][0][0] = $dp[$i - 1][0][0]; $dp[$i][0][1] = max($dp[$i - 1][0][1], $dp[$i - 1][0][0] - $prices[$i]); $dp[$i][1][0] = max($dp[$i - 1][1][0], $dp[$i - 1][0][1] + $prices[$i]); $dp[$i][1][1] = max($dp[$i - 1][1][0] - $prices[$i], $dp[$i - 1][1][1]); $dp[$i][2][0] = max($dp[$i - 1][2][0], $dp[$i - 1][1][1] + $prices[$i]); } $length = count($prices) - 1; return max($res, $dp[$length][0][0], $dp[$length][1][0], $dp[$length][2][0]); }
另外，结合自己做题之路，分享一个好方法，千万千万别一题题做下来，既然刷题当然需要针对性，一定要专门针对性的练习，哪一块数据结构或者算法短板，没关系，先补下知识，然后想刷二分？可以，Leecode (如果你看的是英文版的话，Leetcode-cn 的话更省事了，直接看中文) 首页点击 tags, 选择 Binary Serach, 这样针对性的学习，我想成长只是时间的问题吧。因为你帅我才告诉你。
