思想

时间好快，转眼间到了 5 月。从 3 月开始二刷 Leetcode，到现在过了好久，课内课外许多事情，100 题居然还是没有刷完。很可能是因为我自己对这种不太认同，我不知道刷题到底筛选了什么，服从性测试吧？

不过还是要做，所以今天得空刷一刷动态规划的题目。最早接触动态规划是在算法课上，但是不能理解，不管从算法的名称还是算法内容上都不能理解——哪里动态了？哪里规划了。

其实现在让我总结，动态规划的本质是状态缓存。很多时候我需要复用某些状态的计算结果，把那些算过的结果存储在数组中，并采用某些组织形式，探寻下标规律，得到计算图。

从具体实践上说，动态规划要做两件事：

  1. 明确数组中下标的含义；
  2. 写出状态转移方程。

所谓的下标含义，就是 dp[i][j] 中，i 和 j 分别表示什么，因题而异。状态转移方程则是计算图的体现：当前的 dp[i][j] 依赖于先前得到的哪些数组元素。我们需要有组织地实现这个计算图，所以有时候需要琢磨循环的起始与终止条件。

例题

5. Longest Palindromic Substring

题目的要求是，给一个字符串，找出其中最长的回文子串，这里的子串的意思是，必须要连续排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    string longestPalindrome(string s) {
        // dp[i][j] means that s[i] to s[j] is palindrome
        int n = s.size();

        int start = 0;
        int maxLen = 0;

        vector<vector<bool>> dp(n, vector<bool>(n, false));

        // dp[i][j] depends on dp[i+1][j-1]
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                // same loc, must be true
                if (i == j) {  // this should be considered first
                    dp[i][j] = true;
                } else if (s[i] == s[j]) {  // if s[i] == s[j], look dp[i+1][j-1]
                    if (j - i == 1) {  // neighbor and same, e.g. bb
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                // longest should be stored and updated
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }

        return s.substr(start, maxLen);
    }
};

思路是什么呢？状态缓存的思路。首先，定义状态是什么，想到，应该需要一个二维的状态，来记录从 i 到 j 的子串是否是回文串。之后，有了这个状态，就能推断出 3 种递推情况来计算 dp[i][j]：

  • 如果 i == j，子串的长度是 1，肯定是回文串，无脑赋 true；
  • 如果 s[i] == s[j]，才有后续的比较可能
    • 如果 j - i == 1，二者相邻排列，肯定是回文串；
    • 如果二者并不相邻，中间隔着某个字符串，需要用 dp[i+1][j-1] 来看看它是否是回文串，从而得到最终判断。

很多算法题的题解都说，「自然」，「注意到」这类词语，如果没有这么强的注意力怎么办？其实这个事情没那么好想，我觉得要时刻询问自己两个问题：怎样维护状态？怎样完成状态之间的递推？这两步之间并没有严格的先后关系，而是相互促进的。

从这种思路上来看，动态规划有些类似于回溯法或者递归的感觉：我暂时不知道这个问题该怎么解决，但如果给了我规模减少后的问题，我能得到当前问题的结果。这样传帮带，接力地完成了最终问题的解决。

当然，对这道题而言，如果要获得最终结果，还需要用两个变量存储起始下标和字符串长度，因为单独从 dp 数组中无法得到最终答案。

32. Longest Valid Parentheses

这题给了我们一个字符串，让我们判断其中最长的合法括号子串有多长。这里的子串也是连续的，即 substr。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int longestValidParentheses(string s) {
        // dp[i] stands for max valid paren ends at i
        int n = s.size();

        if (n == 0) return 0;

        vector<int> dp(n, 0);

        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] == ')') {
                if (i - 1 >= 0 && s[i-1] == '(') {
                    dp[i] = 2 + (i - 2 >= 0 ? dp[i-2] : 0);
                } else if (i - 1 >= 0 && dp[i-1]) {
                    int j = i - dp[i - 1] - 1;  // first invalid pos before valid str
                    if (j >= 0 && s[j] == '(') {
                        dp[i] = (i - j + 1) + (j - 1 >= 0 ? dp[j-1] : 0);
                    }
                }
            }

            maxLen = max(maxLen, dp[i]);
        }

        return maxLen;
    }
};

还是想，状态的定义是什么。合法的括号匹配…要么是并列(()())，要么是嵌套((()))。而什么时候需要判断是否发生括号匹配呢？应该是当前指向的字符串为 ) 的时候。匹配的方法是，要么前一个符号是 (，要么能在更前方找到合法的嵌套匹配。

思忖一下，发现这两种匹配如果要依赖先前的状态信息，那状态的含义是「以某个下标为起点，向前走，能找到的最长合法括号子串」。比如 s[i] 表示从下标 i 出发，向 [0] 方向前进，最长能维持多长的合法括号子串。

如果有了这样的状态定义，那么，在并列匹配的时候，如果满足前一个符号是 (，则看看再前一个位置维持的合法子串长度为多少，append 长度。

在嵌套匹配的时候，则需要看看前一个状态维持的合法子串长度几何，越过这个合法长度，看第一个非法字符是否为 (，如果是，则满足嵌套匹配，形成一段佳话，并再看看前一个的 dp 状态，能否延续。

这就是本题的主要思路。当然，还需要用一个特别的变量记录最长长度。

此外，涉及的技巧是，如果从 i = 1 开始，可以让条件更简单。以及，不要忘记判断输入长度为 0 的情况，诶，否则会出问题。

62. Unique Paths

这题给了一个方格图，机器人在左上方，终点在右下方。可以选择向右或者向下走，问有多少种不同的路径。

嗯，我记得组合数学的课上讲过这个例子，是 Catalan 数么？我还记得，小时候上奥数课的时候，似乎讲过这个题目，当时老师告诉我们，可以从终点开始，给路径标 1，之后加和，大概就是动态规划的思路。可惜当时没能理解，说明我这个脑子还是不太适合学奥数。不过早晚要和它见面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));

        dp[m-1][n-1] = 1;  // one way at destination

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (j < n - 1) {
                    dp[i][j] += dp[i][j + 1];
                }
                if (i < m - 1) {
                    dp[i][j] += dp[i + 1][j];
                }
            }
        }

        return dp[0][0];
    }
};

这题的思路非常之简朴，因为网格天然符合动态规划的可视化情境。这里状态的定义是，从 [i][j] 位置走到终点的不同路径数，它可以根据其右侧和下方的路径数得到（前提是可以走右侧或者下方）。而终点，起始条件是 1，随后一个简单的递推便完成咯。

64. Minimum Path Sum

这题和上一题差不多，只不过每个格子的值变成了更多的值，而不是全 1。思路和上一题一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> dp(m, vector<int>(n, 0));

        dp[m-1][n-1] = grid[m-1][n-1];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i != m - 1 || j != n - 1) {
                    dp[i][j] = grid[i][j] + min((i < m - 1 ? dp[i + 1][j] : INT_MAX),
                                                (j < n - 1 ? dp[i][j + 1] : INT_MAX));
                }
            }
        }

        return dp[0][0];
    }
};

这个 if 条件一定要注意，应该是 || 而不是 &&，诶，自己居然犯这种错误…必须 Debug 才发现为什么循环没进去。

此外，这个写法不一定是最好的，比较绕，可以用一些更笨、冗长，但是更直观的做法。

70. Climbing Stairs

爬楼梯，一次可以走一阶或者两阶，问，有多少种不同的路数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);

        dp[n] = 1;  // at destination, one way
        dp[n - 1] = 2;  // define it explicitly could ease loop condition

        for (int i = n - 2; i >= 1; i--) {
            dp[i] = dp[i + 1] + dp[i + 2];  // one step or twp steps
        }

        return dp[1];
    }
};

状态定义是，在当前高度，到达目标有多少种走法。这里把离终点最近的两个高度显式计算出来，因为这样会让循环相对简单一些。此外，定义 dp 数组的长度是 n + 1，容易和语义相对应。

72. Edit Distance

这题很巧妙，问我们如何用最小的次数把字符串 1 变成字符串 2。我们可以对字符串 1 施加 3 种操作：增加、删除或替换字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;  // delete all char in word1
        }

        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;  // add corresponding num of char in word2 to word1
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1]));
                }
            }
        }

        return dp[m][n];
    }
};

对于这种两个字符串的题目，比较自然的想法是用 dp[i][j] 表示字符串 1 的前 i 个字符变成字符串 2 的前 j 个字符需要的最小次数。

之后，对于状态的转移，分成两种情况：

  • 如果当前指向的两个字符相等，直接取字符串 1 前 i-1 个字符和字符串 2 的前 j-1 个字符的操作次数（可以用数学证明不必像另一种情况考虑另外的两个结点再取 min）；
  • 如果字符不等，则考虑其余 3 种前置情形，并 +1 表示当前要做出操作。

对于字符相等的情况，没什么多说的，关于数学证明，我不太想赘述。

而字符不等的情形，这个数学形式好自然！没想到一个最小编辑次数的题目可以这样被解决？怎么理解这里的状态和编辑动作的对应关系？

  • 对于 dp[i-1][j]，这表示 word1 前 i-1 个字符变到 word2 前 j 个字符需要的最小次数，现在我们考虑 word1 的前 i 个变成 word2 的前 j 个，对应删除操作；
  • 对于 dp[i][j-1]，现在 word1 的前 i 个和 word2 的前 j-1 个匹配了，那，和 word2 的前 j 个匹配，需要加个字符；
  • 对于 dp[i-1][j-1]，则对应替换，不必多说。

118. Pascal’s Triangle

这题让我们画一个 Pascal 三角形。

Pascal Triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;

        for (int i = 0; i < numRows; i++) {
            vector<int> row;
            
            for (int j = 0; j < i + 1; j++) {
                // edge
                if (j == 0 || j == i) {
                    row.push_back(1);
                } else {
                    row.push_back(res[i - 1][j - 1] + res[i - 1][j]);
                }
            }

            res.push_back(row);
        }

        return res;
    }
};

嗯，这确实也算是一种动态规划，不过，挺简单，不浪费时间了。

139. Word Break

这题叫分词器，给了一个字符串和一个字符数组，让我们判断某个字符串能不能用字符数组中给定的单词切分完毕，一个单词可以使用多次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(), wordDict.end());

        int n = s.size();

        size_t maxLen = 0;

        // calculate maxLen to boost iteration
        for (string word : words) {
            maxLen = max(maxLen, word.size());
        }

        vector<bool> dp(n + 1, false);

        dp[0] = true; // init condition

        for (int i = 1; i <= n; i++) {
            for (int j = i; j >= 1 && i - j + 1 <= maxLen; j--) {
                if (words.count(s.substr(j - 1, i - j + 1))) {
                    dp[i] = dp[j - 1];
                    if (dp[i]) break;
                }
            }
        }

        return dp[n];
    }
};

思路不算特别难，我认为的难点：

  1. 有关 unordered_set STL 的方法；
  2. 处理下标的逻辑。

先说思路，再逐个解释难点所在。如果我们在处理一个分词任务，比较在意的状态是什么呢？是对于处理到的位置 i，能否被正确分词。因为有了这个状态，当再次处理新位置 j 的时候，怎样判断这个位置是否能被分词？先遍历词典中的每个单词，考察从当前位置回退单词长度时，字符串的那部分子串是否可以被切分。

关于难点 1，怎样快速地考虑词典中的每个单词？一种方法是先变成集合，引入一些额外开销，但是后续的查找是 $O(1)$ 的；另一种思路，可以对每个单词进行遍历，根据其长度判断下标。上方代码展示的是思路 1，需要知道怎么从 vector 构建 unordered_set，以及 count 方法。

关于难点 2，这里 dp[i] 的含义是对于前 i 个字符，因为这样方便把 dp[0] 设定为起始条件。然而，在访问字符串 substr 时，需要进行减一的操作，才能和字符串的操作对应起来。

最后，一个小 trick，可以记录词典中最长的单词的长度，这样当 i 和 j 相距过远，肯定无法匹配任何一个单词时，直接终止。

附赠一个解法 2，我觉得更省事一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();

        vector<int> dp(n + 1, false);
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (string word : wordDict) {
                int wordLen = word.size();

                if (i - wordLen >= 0 && s.substr(i - wordLen, wordLen) == word) {
                    dp[i] = dp[i - wordLen];
                    if (dp[i]) break;
                }
            }
        }

        return dp[n];
    }
};

152. Maximum Product Subarray

这题要求我们找出一个数组的子数组（必须连续），这个子数组元素的乘积最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxVal = nums[0];
        int minVal = nums[0];

        int ans = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < 0) {
                int temp = maxVal;
                maxVal = minVal;
                minVal = temp;
            }

            maxVal = max(maxVal * nums[i], nums[i]);
            minVal = min(minVal * nums[i], nums[i]);

            ans = max(ans, maxVal);
        }

        return ans;
    }
};

如果数组只有正数，那答案是平凡的——把所有元素乘起来就好了。但加上了负数，就需要考虑负负得正的问题。因此对于状态来说，肯定要为每个元素记录一个最大值和最小值。所以，对 dp[i] 来说，含义是到当前位置为止，能获得的最大值和最小值。

递推的逻辑要分成正数和负数讨论：

  • 如果是正数，那当前位置能获得的最大值只取决于前一个位置，大的更大，小的更小；
  • 如果是负数，需要把前一个位置的最大值最小值交换后再乘起来。

因为 subarray 是连续的语义，所以不管怎样，都必须把当前位置的结果乘进来。这样，必须再引入一个变量存储遍历过程中遇到过的最大值。

我觉得这题有些绕，虽然式子很优雅，但逻辑上需要走些弯路。

198. House Robber

聪明的小偷沿着大街走，不能在同一晚入室抢劫两个相邻的屋子，否则会触发警报。问怎样抢能在一晚获得最大的收益。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        if (n == 1) return nums[0];

        vector<int> dp(n, 0);

        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
        }

        return dp[n - 1];
    }
};

思路很简洁。用 dp[i] 来记录到当前下标的房子为止，能获得的最大金额，记住这个语义。

之后，递推关系类似于一个典型的背包问题：

  • 可以选择抢这个屋子，获得了这个屋子的金额，同时意味着必须放弃前一个屋子的累计结果，只能累加到向前两个屋子的金额上；
  • 选择不抢这个屋子，那便单纯继承了前一个屋子为止获得的金额。

我做这道题的时候有一个疑问，不知道为什么当选择抢这个屋子的时候，直接就把 dp[i-1] 排除在外了。因为根据我们之前设定的语义，dp[i-1]仅仅表示到下标为止获得的金额，并不一定意味着我们抢了这个屋子。其实可以进一步推理：

  • 如果真的抢了这个屋子，那肯定不能计入这种情况，dp[i-2] 是对的；
  • 如果没抢这个屋子，那应该统计 dp[i-1]，不过根据递推关系，没抢这个屋子如果更优，意味着直接继承了 dp[i-2] 的结果，所以和上面的情形一致。

279. Perfect Squares

这题给了一个数字，问最少多少个平方数加起来能得到这个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;

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

        return dp[n];
    }
};

思路是，用 dp[i] 表示得到 i 需要的最少平方数个数。那么递推关系是，考虑所有比 i 小的平方数，求得 i - 平方数 后的次数再加 1，作为得到当前数的个数，取最小的便 OK。

300. Longest Increasing Subsequence

这题要求找出最长递增子序列，这里的子序列不要求连续。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int ans = 1;

        vector<int> dp(n, 1);  // seq length

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }

            ans = max(ans, dp[i]);
        }

        return ans;
    }
};

用 dp[i] 表示以当前子串为结尾，获得的最长递增子序列长度。这样递推的关系是，对于某个位置，考虑其先前的所有位置，如果先前位置的值小于该位置，则可以考虑更新当前值。

发现了没有？在动态规划中，很多时候对于 dp[i] 的定义是以该位置结尾时，获得的结果，即必须使用当前元素。这和到该位置为止时，能获得的最优值是两码事请。后者要求不减，前者不一定满足。

322. Coin Change

找零。问最少可以用几个硬币凑出给定数额。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);

        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i - coin] != INT_MAX) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

我记得最早试图了解算法竞赛的时候，就看过这道题，当时对这个题目的题解完全无法理解，以及为什么贪心算法在这里不适用。现在比之前稍微清楚了些。

这题的思路是，用 dp[i] 表示为了获得当前金额需要使用的硬币数量，如果凑不出来，用 INT_MAX。递推的思路是，考虑所有能用的硬币种类，减去硬币金额后的数值如果能凑出来，则考虑更新当前值。

需要注意的地方是对于下标的合法判断，以及涉及 INT_MAX 的转换。

416. Partition Equal Subset Sum

分割相等子集和。把一个集合分成两个子集，这两个子集能否大小相等？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum % 2) return false;

        int half = sum / 2;
        int n = nums.size();

        vector<bool> dp(half + 1, false);

        dp[0] = true;

        for (int num : nums) {
            for (int i = half; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }

        return dp[half];
    }
};

第一次做这道题是很惊艳的，因为如果直来直去，会想到怎么把子集分成相等的两半。但其实这道题需要绕个弯子，直接找能否从集合中挑出一些元素，使得它们的和是集合总和的一半即可。

这道题还有一个难点是，要确保每个元素只能使用一次。所以在循环遍历的时候，要以集合中的元素为外层循环，确保每个只使用一次。之后，在内层遍历的时候也要小心，从高到低，保证不会重复使用当前元素多次。

补充，dp[i] 的语义是，是否能从集合中挑出一些元素，使得它们的和是 i。

1143. Longest Common Subseqence

最长共同子序列。给了两个字符串，找出它们最长的共同子序列。这里的子序列也不要求连续。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                } else {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        return dp[m][n];
    }
};

这道题也是非常神奇。如果没有了解过动态规划，会觉得简直无法高效地计算。然而，如果考虑状态 dp[i][j] 是第一个字符串前 i 个字符和第二个字符串前 j 个字符中的最长子序列个数，那么，递推关系就可以根据当前指向的两个字符是否相等来分别讨论。

这种两个字符串的动态规划基本上是一个套路，就像 Edit Distance 那道题。

刷了很多动态规划，感觉，自己有时候也陷入了一个思维定式：为什么要用它？是个要考虑的地方。毕竟机试可不会分专题进行。