Nov 20, 2024

LeetCode刷题笔记 - 动态规划

Xinyu Li

GrindingLeetCode

4499 Words 20 Minutes, 27 Seconds

2024-11-20 19:41 -0800

概述

动态规划

DP五步：

  • 状态表示什么（dp 数组含义）？

  • 状态如何转移（递推公式）？

  • 初始状态是什么？

  • 确定遍历顺序。

  • 举例推导 dp 数组。

动态规划可以分为以下几类（参考这篇文章和这篇文章)

基础DP

状态用一维数组存储，状态转移比较明显，即题目有明显的”从状态A转向状态B“的描述。比如帕楼梯，从台阶\(i\)爬到台阶\(j\)。

背包 DP

基础理论

有n个物品和容量为W的背包，每个物品有重量weight[i]和价值value[i]两种属性。要求选取若干物品放入背包，使得总价值最大且不超过背包重量。

0-1背包

在上述题目基础上，每个物品只能选一次。

二维DP

构造(n, W)二维DP数组dp。dp[i][j]表示

在物品0到物品i中选择，容量为j的背包所能装下的最大价值为dp[i][j]。

到达dp[i][j]的方式有两种：

  1. 不放物品i

    则最大价值为只能选前i-1个物品，容量为j的背包所能装下的最大价值

  2. 放物品i

    则最大价值为value[i]加上选前i-1个物品，容量为j-weight[i]的背包所能装下的最大价值

对应的状态转移方程为

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]])

对应的核心代码为

// We declare a 2d array of size (n+1, W) for convenience
for (int i = 0; i < n; i++) {
    for (int j = W - weight[i]; j < W; j++) {
        dp[i+1][j+1] = max(dp[i][j], dp[i][j-weight[i]] + value[i]])
    }
}

滚动数组

考虑空间复杂度，我们可以用滚动数组代替二维数组。

对于当前的i，dp[j]表示选前i个物品，容量j的背包所能装下的最大价值。

对应的核心代码为

// We declare a 1d array of size W
for (int i = 0; i < n; i++) {
    for (int j = W-1; j >= weight[i]; j--) {
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

值得注意的是，里面一层循环是从后往前的。这是因为dp[i][j]是由dp[i-1][j]和dp[i-1][j-weight[i]]决定的。从后往前更新一维数组时，在对i更新到dp[j]时，dp[j-weight[i]]还没有被更新，仍然是i-1时更新的结果，此时的dp[j-weight[i]]表示“选前i-1个物品，容量为j-weight[i]的背包所能装下的最大价值”。

完全背包

完全背包中，物品可被选择无数次。

由上文滚动数组的分析，我们可以引申出完全背包的滚动数组解法：和0-1背包类似，但从前往后更新滚动数组。

这是因为从前往后更新，对i更新到dp[j]时，dp[j-weight[i]]已经是对i更新后的结果，其含义为“选前i个物品，容量为j-weight[i]的背包所能装下的最大价值”。

在上述题目基础上，每个物品可以选取无数次。

416. Partition Equal Subset Sum

思路：目标和tgt_sum为nums总和的一半。则可以把问题转换为对于容量为tgt_sum的背包，让weight[i] = value[i] = nums[i]。如果最大价值等于tgt_sum，则表示可以等分集合。

1049. Last Stone Weight II

考虑题目给出的例1，石头相撞的过程如下

We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

可以表示成

Given [2, 7, 4, 1, 8, 1]
4 - 2 => [(4-2), 7, 1, 8, 1]
8 - 7 => [(4-2), 1, 1, (8-7)]
(4-2) - 1 = 2 - 1 => [(4-2-1), 1, (8-7)]
(4-2-1) - 1 = 1 - 1 => [(8-7)]

The entire process is the same as saying 
4 - 2 - 1 - 1 + 8 - 7 = 1

上述过程可以被解释为“加或减每个数组中的数字，所能得到的最小非负值”。

这一过程也可以被解释为“分割数组为两个子数组，求两个子数组之和的最小差值”。这就回到了416的分割子集的思路。

494. Target Sum

题目可以这样理解：将数组分割成两个子数组，各自的和分别为x和y（不妨设x > y）。求能满足x-y=target的分割方法的数量。

已知x+y=sum(nums), x-y=target，则可知y=(sum(nums)-target)/2，题目可以等价为求出在数组中任选数字、其和为y的选择方法数量。

dp[j]表示选前i个物品，可以填满容量为j的背包的选择方法的数量。对应的状态转移方程为dp[i][j] = dp[i-1][j] + dp[i-1][j-weight[i]]。

474. Ones and Zeroes

dp是大小为(m+1, n+1)的二维滚动数组。

对于当前的i，dp[j][k]表示在前i个字符串里选择，能满足at most j 0's and n 1's in the subset的最大子集大小。

状态转移方程为dp[j][k] = max(dp[j][k], dp[j-count_0[i]][k-count_1[i]])，即选或不选strs[i]得到的最大子集大小。

518. Coin Change II

比较明显的完全背包。一个注意的点是dp数组得是uint64_t，否则在存储中间结果时会integer overflow。

377. Combination Sum IV

很有意思的一个问题。如果求所有可能的排列 / 组合，那么就只能回溯。但这道题求的是排列的数量，就能DP。

另外，用DP可以求完全背包的排列数量和组合数量，其代码正好是相反的。

首先明确一下定义：排列（permutation）是有顺序的，组合（combination）是没有顺序的。(1, 5)和(5, 1)是同一个组合，不同的排列。

对于完全背包的组合数量，我们先循环物品，再循环背包。

for (int i = 0; i < nums.size(); i++) {
    for (int j = nums[i]; j <= capacity; j++) {
        dp[j] = dp[j] + dp[j - nums[i]];
    }
}

这一写法会使最后的选择方案里，物品必然按照nums的顺序排序。假如nums = {1, 2, 3, 4, 5}，那么就不可能出现5在1前的方案。换句话说，对于属于统一组合的不同排列，我们只取按照物品排序和nums相同的方案（这一方案显然是唯一的）。

对于完全背包的排列数量，我们先循环背包，再循环物品

for (int j = 0; j <= capacity; j++) {
    for (int i = 0; i < nums.size() && nums[i] <= j; i++) {
        dp[j] = dp[j] + dp[j - nums[i]];
    }
}

这一写法则保证了在考虑dp[j]时，dp[k]， k < j的方案数量时考虑了全部物品的方案数量。

322. Coin Change

At i, dp[j] is the fewest number of coins needed to reach amount j considering coins[0] to coins[i].

279. Perfect Squares

物品的重量是完全平方数，每个物品价值为1，背包总容量是n，完全背包。

对于当前i，dp[j]表示在完全平方数1^2, 2^2, ... i^2中选择，总和为j，所需要的最小数量。

例如，对于i = 2，dp[12] = 3，对应的选择为4 + 4 + 4；而对于i = 3，dp[12] = 2，对应的选择是4 + 9。

状态转移方程为

for (int i = 1; i * i < n; i++) {
    for (int j = i * i; j < dp.size(); j++) {
        dp[j] = min(dp[j], dp[j - i*i] + 1);
    }
}

139. Word Break

背包的物品是wordDict中的单词，考虑到这道题要判断的是单词的组合（而非排列）能否构成字符串，我们需要按照组合背包的方法写代码，即先循环背包容量、后循环物品。

dp[j]的含义为：wordDict中的所有单词能否构成字符串s[:j]。状态转移时需要判断s[:j-cur_word.size()]能否被构成，以及s[j-cur_word: cur_word]和cur_word是否相等。

核心代码为

dp[0] = true;

for (int j = 1; j < dp.size(); j++) {
    for (int i = 0; i < wordDict.size(); i++) {
        if (dp[j]) {
            // s[:j] can be constructed using words in wordDict[:i]
            break;
        }
        const string& cur_word = wordDict[i];
        if (j < cur_word.size()) {
            continue;
        }
        const string& cur_substr = s.substr(j - cur_word.size(), cur_word.size());
        // State Transition
        dp[j] = dp[j - cur_word.size()] && (cur_word == cur_substr);
    }
}

打家劫舍

198. House Robber

dp数组含义如下:

  • dp[i][0]表示不打劫第i间房时，最大收益

  • dp[i][1]表示打劫第i间房时，最大收益

状态转移方程为

dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
// Since we can't rob two adjacent houses, we must not rob house i-1 if we rob house i
dp[i][1] = dp[i-1][0] + nums[i-1];

213. House Robber II

在环上打劫，不能打劫相邻住户。可以分类处理问题。由于不能同时打劫第0和n家，我们可以将问题分类为

  • 打劫第0家：只能打劫第0到n-1家。

  • 不打劫第0家：只能打劫第1到n家。

337. House Robber III

在树上打劫，不能打劫在树上直接相连的住户。后序dfs遍历树，每个节点计算两个状态

  • 不打劫该节点，考虑所有子节点和当前节点，最大收益

  • 打劫该节点，考虑所有子节点和当前节点，最大收益

由于是后序遍历，考虑当前节点时，已经计算出左右字节点的两个状态，故可以推出当前状态。

状态转移方程为

vector<int> left_vals = postorder(cur->left);
vector<int> right_vals = postorder(cur->right);
return {
    *max_element(left_vals.begin(), left_vals.end()) + *max_element(right_vals.begin(), right_vals.end()),
    left_vals[0] + right_vals[0] + cur->val
};

股票

有通解。

子序列

72. Edit Distance

dp[i][j]表示word1[:i]和word2[:j]的最小编辑距离，0 <= i <= len(word1)，0 <= j <= len(word2)

基于递推的思路，我们只需要考虑三种可能的编辑方式：

  1. 删除word1[i-1]，然后编辑word1[:i-1]至word2[:j]

  2. 在word1末尾插入word2[j-1]，然后编辑word1[:i]至word2[:j-1]

  3. 编辑word1[:i-1]至word2[:j-1]，如有必要再将word1[i-1]替换为word2[j-1]

由此可得状态转移方程

dp[i][j] = min(
    dp[i-1][j] + 1,
    dp[i][j-1] + 1,
    dp[i-1][j-1] + int(word1[i-1] != word2[j-1])
)

初始化方式为

dp[0][j] = j
dp[i][0] = 0

647. Palindromic Substrings

这道题不能使用类似于“以i结尾的子字符串”去做，找不到明显的递推关系。

回文的递推关系：对于q - p > 2，如果s[p: q]是回文，且s[p-1] == s[q]，那么s[p-1: q+1]是回文。

由此可得dp[i][j]的含义为s[i: j+1]（以s[i]开始，s[j]结束的子字符串）是否为回文，对应的状态转移方程为

// when 0 <= j-i < 2 (1 or 2 char, not applicable for recursion)
dp[i][j] = s[i] == s[j]
// when j-i > 2, s[i: j+1] depends on s[i+1: j]
dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

值得注意，dp[i][j]依赖于dp[i+1][j-1]，所以更新顺序应该为i从大到小，j从小到大，且根据区间的定义，i <= j。

516. Longest Palindromic Subsequence

基本思路和上题一样，dp[i][j]表示的是区间，递推是从小区间推到大区间。

dp[i][j]表示s[i-1: j]的最长回文长度。

值得注意的是，对于s[i-1: j]的最长回文长度，不同于上题，我们需要看三个子区间:s[i-1: j-1]，s[i: j]，如果s[i-1] == s[j+1]，那还需要考虑s[i-1: j]。比如说bbbaab，在计算bbaa的最长回文长度时，我们需要考虑bba，baa。只看中间的ba是不够的。

由此可得状态转移方程为

dp[i][j] = max({
    dp[i+1][j],
    dp[i][j-1],
    dp[i+1][j-1] + (s[i-1] == s[j-1]) * 2
});

与上题相同，更新顺序应该为i从大到小，j从小到大，且根据区间的定义，i <= j。

区间 DP

树形 DP

树的定义是“无环无向连通图”。在树上DP，可以对树后序遍历，当前节点的状态由子节点状态推出。

968. Binary Tree Cameras

Hard题。虽然做了三个小时，但最后居然真的做出来了…

代码随想录里把这道题划分到了贪心，但我用dp也能做的出来。

等有精力了再研究一下贪心的解法…

我的整体思路是后序遍历整颗树，每个节点的状态由其直接子节点推出。

每个节点有三个状态

  • dp[node_ptr][0]: 没有摄像头、未被子节点监视时，最小摄像头数

  • dp[node_ptr][1]: 没有摄像头，但被子节点监视时，最小摄像头数

  • dp[node_ptr][2]: 有摄像头时，最小摄像头数量

状态转移的方式如下

// cur has no cam and is not monitored 
// => left and right has no cam, and they must be monitored by child
dp[cur][0] = dp[cur->left][1] + dp[cur->right][1];
// cur has no cam but is monitored by child 
// = left or right or both have cam, and whichever has no cam must be monitored by child
dp[cur][1] = min({
    dp[cur->left][2] + dp[cur->right][1], 
    dp[cur->left][1] + dp[cur->right][2],
    dp[cur->left][2] + dp[cur->right][2]
});
// cur has cam
// min among all possible combination of states of left and right
dp[cur][2] = 
        *min_element(dp[cur->left].begin(), dp[cur->left].end()) 
    +   *min_element(dp[cur->right].begin(), dp[cur->right].end()) 
    +   1

然而事情并没有这么简单。有一些情况下，是会存在非法的状态的。考虑以下树中的A节点。dp[A][0]就是一个非法的状态。如果dp[A][0]合法，那就意味着A没有摄像头，也没有子节点监视A，由此可知A、B、C都没有摄像头，这会导致B和C无法被任何节点监视到。

        [A]
      /     \
    [B]     [C]

为了解决这一问题，我们可以使用一个很大的数字表示非法状态。题干中节点数量范围为\([1,1000]\)，摄像头数量最多为1000。所以我们可以用10000表示非法状态。在初始化叶子节点时，dp[node][1]就是非法状态，因为叶子节点没有子节点，不可能被子节点监视。因此，有以下代码

if (cur->left == nullptr || cur->right == nullptr) {
    auto child = cur->left == nullptr ? cur->right : cur->left;
    dp[cur][0] = dp[child][1];
    dp[cur][1] = dp[child][2];
    dp[cur][2] = *min_element(dp[child].begin(), dp[child].end()) + 1;
} else {
    // 上述状态转移的代码
}

See Also