分割类问题也算是动态规划的常客。对于字符类问题，状态转移方式往往依赖于相邻的位置。

0-1背包问题，状态方程不仅依赖于相邻的位置，还依赖于满足条件的空间位置。

对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割条件的位置。

类型特点

股票买卖类问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：

1
2
3
4
5
6
7
8
9

dp[i][k][0 or 1]
0 <= i <= n - 1, 1 <= k <= K
n 为天数，大 K 为交易数的上限，0 和 1 代表是否持有股票。
此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

三种背包问题

背包问题主要分为三种：

• 0-1 背包问题：
  • 定义：给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
  • 变种的子集背包问题定义：给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？
• 完全背包问题：
  • 定义：0-1 背包问题中，每个物品最多可以装一次。完全背包中，所有物品的数量是无限的。
  • 因为物品的数量没有限制，因此使用基于贪心策略来做。 循环判断「剩余空间下可容纳的最高性价比物品」，并加入背包。

定义

根据 Leetcode 的习惯，子序列（subsequence）不必连续，子数组（subarray）或子字符串（substring）必须连续。

动态规划中，子串子序列的问题大概分为如下几种：

• 单条数组(字符)内部的对比，比如:

  • 5. 最长回文子串 + 516. 最长回文子序列
  • 300. 最长递增子序列 + 674. 最长连续递增序列（不使用动态规划反而更简单一些）

• 两条数组(字符)之间做对比，比如

  • 1143. 最长公共子序列 和 最长公共子串 (leetcode 上没有这个题，随便找了一个)
  • 72. 编辑距离

《算法导论》这门课的老师是黄刘生和张曙，两位都是老人家了，代课很慢很没有激情，不过这一章非常有意思。