AllenY's blog

LeetCode刷题记录（动态规划篇），个人向。

[70] Climbing Stairs

难度：Easy
语言：C++

题目描述。
第i层可以从i - 1层跳一步或者从i - 2层跳两步，所以有dp[i] = dp[i - 1] + dp[i - 2];。
注意我们这里不关心dp[0]是多少。因为按照定义，应该有dp[0] = 0，但是又应该要dp[0] = 1才能递归正确。实际上这道题n是大于等于1的，所以dp[0]也正好没有意义。我们直接初始化dp[1]和dp[2]，然后从dp[3]开始计算即可。

class Solution {
  public:
    int climbStairs(int n) {
        if (n <= 1) {
            return n;
        }
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < n + 1; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

[118] Pascal's Triangle

难度：Easy
语言：C++

题目描述。
就按照杨辉三角形（英文这边叫Pascal’s Triangle）定义一行一行算即可，类似动态规划已经把状态转移方程告诉你，直接填表就行了，无思考难度。
我们先把每一行的最左右两边填上1（result[i][0] = result[i][i] = 1;），然后再依次填中间的，省去了边界特殊情况判断的麻烦。

class Solution {
  public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result(numRows);
        for (int i = 0; i < numRows; ++i) {
            result[i].resize(i + 1);
            result[i][0] = result[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
            }
        }
        return result;
    }
};

[198] House Robber

难度：Medium
语言：C++

题目描述。
比较基础的动态规划，代码照着写就完事。

• 状态转移方程$dp[i] = \max (dp[i-2] + nums[i], dp[i -1])$。
• 初始状态$dp[0] = nums[0], dp[1] = \max (nums[0], nums[1])$。

class Solution {
  public:
    int rob(vector<int> &nums) {
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
};

[279] Perfect Squares

难度：Medium
语言：C++

题目描述。

• 状态转移方程$dp[i] = \min (dp[i - j^2] + 1, dp[i]), \forall j * j <= i$
• 初始状态$dp[0] = 0$

代码照着写就完事。

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 - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};

[322] Coin Change

难度：Medium
语言：C++

题目描述。

• 状态转移方程$dp[i] = \min (dp[i - c] + 1, dp[i]), \forall c <= i$
• 初始状态$dp[0] = 0$

就上题的状态转移方程稍微改一丢丢，一类题，没什么区别。
需要注意的是若无解需要返回-1，所以需要额外注意一下dp值为__INT_MAX__的情况。

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 c : coins) {
                if (c <= i && dp[i - c] != __INT_MAX__) {
                    dp[i] = min(dp[i - c] + 1, dp[i]);
                }
            }
        }
        return dp[amount] == __INT_MAX__ ? -1 : dp[amount];
    }
};

[139] Word Break

难度：Medium
语言：C++

题目描述。

• 状态转移方程$dp[i] = dp[j] \wedge (s[j:i-1]\in wordDict), \forall j\in [0, i)$
• 初始状态$dp[0] = true$
  代码照着写就行。取子串用substr，然后查找用find。
  注意这里i表示的是考虑的字符串的长度，而j是suffix的起始位置。
  此外这里把!dp[i]条件放入了内层for循环条件判断，一方面该判断的存在可提前结束循环，减少计算，另一方面写法又精简了代码。

class Solution {
  public:
    bool wordBreak(string s, vector<string> &wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i && !dp[i]; ++j) {
                string suffix = s.substr(j, i - j);
                dp[i] = dp[j] && find(wordDict.begin(), wordDict.end(),
                                      suffix) != wordDict.end();
            }
        }
        return dp[n];
    }
};

[300] Longest Increasing Subsequence

难度：Medium
语言：C++

题目描述。

• 状态转移方程$dp[i] = \max (dp[j] + 1, dp[i]), \forall nums[i] > nums[j]$
• 初始状态$dp[i] = 1, \forall i\in [0, n-1]$

代码照着写就行。
此外，注意题目要返回的是最长递增子序列的长度，因此要返回的不是dp[n-1]，而是需要记录一下值最大的那个dp[i]，然后返回该值。
最后，这道题还有$O(nlogn)$时间复杂度的解法，可参考这篇solution。但本人这里主要关注动态规划，因此这种解法不做研究。

class Solution {
  public:
    int lengthOfLIS(vector<int> &nums) {
        int n = nums.size();
        int ret = 1;
        vector<int> dp(n, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

[152] Maximum Product Subarray

难度：Medium
语言：C++

题目描述。
因为“负负得正”情况的存在，我们需要同时记录和考虑最小值和最大值。
这里我们使用dpMin[i]表示以nums[i]结尾的乘积最小子数组的乘积，使用dpMax[i]表示以nums[i]结尾的乘积最大子数组的乘积。

• 状态转移方程$dpMin[i] = \min ({dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i], nums[i]})$
• 初始状态$dpMin[0] = nums[0], dpMax[0] = nums[0]$

最后返回dpMax中最大的那一个即可。

class Solution {
  public:
    int maxProduct(vector<int> &nums) {
        int n = nums.size();
        vector<int> dpMin(n);
        vector<int> dpMax(n);
        dpMin[0] = nums[0];
        dpMax[0] = nums[0];
        int ret = nums[0];
        for (int i = 1; i < n; ++i) {
            dpMin[i] =
                min({dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i], nums[i]});
            dpMax[i] =
                max({dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i], nums[i]});
            ret = max(ret, dpMax[i]);
        }
        return ret;
    }
};

[416] Partition Equal Subset Sum

难度：Medium
语言：C++

题目描述。
把halfSum看做背包容量，num同时看做物品重量与价值，这道题便是0-1背包问题。
0-1背包问题可使用二维动态规划求解，可参考这篇solution。但实际上，每一行的dp值只与上一行的dp值相关，因此在这里我们使用滚动数组的方式，将空间复杂度降到$O(target)$。
需要注意的是，第二层的循环我们需要从大到小计算，因为如果我们从小到大更新 dp 值，那么在计算 dp[j] 值的时候，dp[j−nums[i]] 已经是被更新过的状态，不再是上一行的 dp 值。

• 状态转移方程$dp[j]=dp[j] ∣ dp[j−nums[i]]$
• 初始状态dp[0] = true

class Solution {
  public:
    bool canPartition(vector<int> &nums) {
        int halfSum = 0;
        int n = nums.size();
        for (int num : nums) {
            halfSum += num;
        }
        if (halfSum % 2 == 1) {
            return false;
        }
        halfSum /= 2;

        vector<bool> dp(halfSum + 1);
        dp[0] = true;
        for (int num : nums) {
            for (int i = halfSum; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[halfSum];
    }
};

[32] Longest Valid Parentheses

难度：Hard
语言：C++

题目描述。
这道题标的是Hard难度，但实际上比想象简单很多，即只要把状态转移方程写出来即可。
我们使用dp[i]表示以s[i]结尾的最长有效括号长度。如果s[i]是'('，那么dp[i]只能是0，因此我们只需要考虑s[i]为')'的情况。
对于s[i]为')'的情况，我们需要找到s[i]前面紧挨着的（即以s[i-1]结尾的）最长有效括号长度，然后再看前面的这个最长有效序列的上一个字符是不是'('，如果是，则长度要加上新的这对括号即+2。最后我们还要拼上更早的有效序列长度，即dp[i−dp[i−1]−2]。
简单来说，对于有效括号序列"...(...)"，两个括号对应+2，括号里的...对应dp[i-1]，最早的...对应dp[i−dp[i−1]−2]，因此有dp[i] = dp[i−1]+dp[i−dp[i−1]−2]+2。
官方题解把字符串分为了“……()”和“……))”两种情况讨论。但实际上，这两种情况完全可以合并为一种。如果是“……()”的情况，那么dp[i−1]就是0，dp[i−dp[i−1]−2]就是dp[i-2]，因此dp[i−1]+dp[i−dp[i−1]−2]+2就等价于dp[i−2]+2。

• 状态转移方程$dp[i] = dp[i−1]+dp[i−dp[i−1]−2]+2, \forall s[i] == ')' \wedge s[i - dp[i - 1] - 1] == '('$
• 初始状态$dp[i] = 0, \forall i$

加上一些边界条件的判断，便得到如下代码。

class Solution {
  public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if (n < 2) {
            return 0;
        }
        vector<int> dp(n, 0); // Defaults to 0
        int maxLength = dp[0];
        for (int i = 1; i < n; ++i) {
            int leftIndex = i - dp[i - 1] - 1;
            if (s[i] == ')' && leftIndex >= 0 && s[leftIndex] == '(') {
                dp[i] = dp[i - 1] + 2 + (leftIndex > 0 ? dp[leftIndex - 1] : 0);
                maxLength = max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }
};

[62] Unique Paths

难度：Medium
语言：C++

题目描述。
非常简单基础的多维动态规划。简单的递推公式，简单的实现。
这里直接在初始化的时候就把所有值初始化为1，避免了后续对第一行和第一列的冗余初始化。

• 状态转移方程$dp[i][j] = dp[i - 1][j] + dp[i][j - 1], \forall 1 \le i < m, 1 \le j < n$
• 初始状态$dp[0][j] = 1, dp[i][0] = 1, \forall 0 \le i < m, 0 \le j < n$

class Solution {
  public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));

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

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

[64] Minimum Path Sum

难度：Medium
语言：C++

题目描述。
和上一题一样实际属于简单题。简单的递推公式，简单的实现。

• 状态转移方程
  • $dp[0][i] += dp[0][i-1], \forall 1 \le i < n$
  • $dp[i][0] += dp[i - 1][0], \forall 1 \le i < n$
  • $dp[i][j] += min(dp[i - 1][j], dp[i][j - 1]), \forall 1 \le i < m, 1 \le j < n$
• 初始状态$dp[i][j] = grid[i][j], \forall 0 \le i < m, 0 \le j < n$

class Solution {
  public:
    int minPathSum(vector<vector<int>> &grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(grid);

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

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

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

[5] Longest Palindromic Substring

难度：Medium
语言：C++

题目描述。
主要难点在于填表的顺序该怎么规定怎么写。由于dp[i][j]需要用到dp[i+1][j-1]，这里我们用子串长度l作为外层循环变量，子串起点i作为内层循环变量，从短的子串最后填表到长的子串，以满足填表的顺序要求。

• 状态转移方程$dp[i][j] = (s[i] == s[j] \wedge (l > 2 ? dp[i + 1][j - 1] : true))$
• 初始状态$dp[i][i] = true, \forall 0 \le i < n$

class Solution {
  public:
    string longestPalindrome(string s) {
        int n = s.size();
        int startIndex = 0, length = 1;
        vector<vector<bool>> dp(n, vector<bool>(n, true));
        for (int l = 2; l <= n; ++l) {
            for (int i = 0; i + l - 1 < n; ++i) {
                int j = i + l - 1;
                dp[i][j] = s[i] == s[j] && (l > 2 ? dp[i + 1][j - 1] : true);
                if (dp[i][j] && l > length) {
                    startIndex = i;
                    length = l;
                }
            }
        }
        return s.substr(startIndex, length);
    }
};

[1143] Longest Common Subsequence

难度：Medium
语言：C++

题目描述。
如果text1和text2的当前字符一样，则最长公共子序列的长度为dp[i-1][j-1]加上1即当前匹配的字符，否则把之前的最长公共子序列即max(dp[i-1][j], dp[i][j-1])传递过来。
为了实现方便，这里dp[i][j]表示的是text1的$[0, i-1]$这部分子串和text2的$[0, j-1]$这部分子串的最长公共子序列，即当我们要填dp[i][j]时，我们要对比的是text1[i-1]和text2[j-1]而不是text1[i]和text2[j]。我们让这样一来，我们可以直接初始化dp整个表格为0（主要目的是为了直接初始化第一行和第一列为0），省去了专门的初始化步骤，也省去了填表时对于第一行第一列的特殊判断。

• 状态转移方程
  • $dp[i][j] = dp[i-1][j-1] + 1, \forall text1[i-1] == text2[j-1], 1 \le i \le m, 1 \le j \le n$
  • $dp[i][j] = \max (dp[i-1][j], dp[i][j-1]), \forall 1 \le i \le m, 1 \le j \le n$
• 初始状态$dp[0][j] = 0, dp[i][0] = 0, \forall 0 \le i \le m, 0 \le j \le n$

class Solution {
  public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i < m + 1; ++i) {
            for (int j = 1; j < n + 1; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

[72] Edit Distance

难度：Medium
语言：C++

题目描述。
经典的编辑距离问题，本科生和研究生的算法课都讲过一次的内容。
在该题目中，替换和增加删除的成本都是1。如果不是1，公式也只需要稍加修改即可。

• 状态转移方程

$dp[i][j] = \begin{cases} j & \text{if } i = 0 \\ i & \text{if } j = 0 \\ \min \begin{cases} \alpha_{x_i y_j} + dp[i-1][j-1] \\ 1 + dp[i-1][j] \\ 1 + dp[i][j-1] \end{cases} & \text{otherwise} \end{cases}$

最后得出代码如下。

class Solution {
  public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < m + 1; ++i) {
            dp[i][0] = i;
        }
        for (int j = 0; j < n + 1; ++j) {
            dp[0][j] = j;
        }

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

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

总结

动态规划总体来说是比较容易的内容，没有哪道题卡了很久，也基本都是类似的套路。
无论是一维还是多维动态规划，都有以下类似的步骤：

• 思考dp表格的含义，定义出dp表格
• 思考出状态转移方程
• 通过状态转移方程，得出填表顺序
• 通过填表顺序，得出哪些状态应该是初始状态，并对初始状态做初始化
• 按填表顺序和状态转移方程填表
• 根据题目定义找到所需的返回结果并返回

基本每道题都按如上套路即可，因此没太多讨论意义。只需要注意一下在[416] Partition Equal Subset Sum中我们使用滚动数组的方式（本质是利用了填表顺序的特性，即下一行最多只依赖上一行的内容），将原本的二维动态规划压缩到了一维的空间复杂度。