动态规划 Dynamic Programming

视频1：动态规划入门：从记忆化搜索到递推【基础算法精讲 17】

视频2：0-1背包 完全背包【基础算法精讲 18】

视频3：最长公共子序列 编辑距离【基础算法精讲 19】

视频4：最长递增子序列【基础算法精讲 20】

视频5：买卖股票的最佳时机：无限次/冷冻期/k次【基础算法精讲 21】

视频6：区间 DP：最长回文子序列 最优三角剖分【基础算法精讲 22】

从记忆化搜索到递推

0-1背包：

    这是0-1背包问题的模版，是“拿或不拿”问题的直译。

完全背包：

    和0-1背包很相像，区别是某一件物品可以重复选，这是这类题的模版。

    另外需要自己额外注意一下动态规划的时候是否需要倒序进行，参见灵神视频。而且一般题目分为至多装capacity，恰好装满capacity和至少装capacity三种不同的变形，也需要代码进行相应的调整。

最长公共子序列&编辑距离

最长递增子序列

    另外值得一提的是：数组 nums 的最长递增子序列（LIS）等价于 nums 与排序去重后的 nums 的最长公共子序列（LCS）：（例如 nums = [1,3,3,2,4]，排序去重后 = [1,2,3,4]，LCS = [1,3,4] 或 [1,2,4]）

状态机 DP

    这里可以把 j-1 写在 dfs(i-1, j-1, 1) + prices[i] 中，然后 dfs(i-1, j, 0) - prices[i]，或者反过来也一样，因为有【买入】肯定有【卖出】：

区间 DP