LeetCode Hot100 DP

Posted on

爬楼梯

Problem

https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-100-liked

Solution

爬到i阶楼梯的方法数等于i-1阶的方法数加i-2阶的方法数。第0阶和第1阶的方法数均为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int climbStairs(int n) {
        int pre0 = 1, pre1 = 1;
        for (int i = 2; i <= n; i ++)
        {
            int cur = pre0 + pre1;
            pre0 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
};

杨辉三角

Problem

https://leetcode.cn/problems/pascals-triangle/?envType=study-plan-v2&envId=top-100-liked

Solution

杨辉三角边缘为1，内部data[row][col] = data[row-1][col-1] + data[row-1][col]。

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

        for (int row = 0; row < numRows; row ++)
        {
            int len = row + 1;
            ans[row].assign(len, 1);

            for (int col = 1; col < len-1; col ++)
            {
                ans[row][col] = ans[row-1][col-1] + ans[row-1][col];
            }
        }
        return ans;
    }
};

打家劫舍

Problem

https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=top-100-liked

Solution

到第i间屋子时可偷的最大金额=max（到第i-1间屋子时可偷的最大金额，到第i-2间屋子时可偷的最大金额+当前屋子金额）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int pre0 = nums[0], pre1 = max(nums[1], pre0);

        for (int i = 2; i < n; i ++)
        {
            int cur = max(pre1, pre0 + nums[i]);
            pre0 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
};

完全平方数

Problem

https://leetcode.cn/problems/perfect-squares/?envType=study-plan-v2&envId=top-100-liked

Solution

当前数的最小完全平方数的数量 = min(当前数-某最小完全平方数)+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numSquares(int n) {
        vector<int> count(n+1, n);
        count[0] = 0;
        for (int i = 1; i <= n; i ++)
        {
            for (int j = 1; j * j <= i; j ++)
            {
                count[i] = min(count[i], count[i-j*j] + 1);
            }
        }
        return count[n];
    }
};

零钱兑换

Problem

https://leetcode.cn/problems/coin-change/?envType=study-plan-v2&envId=top-100-liked

Solution

当前总金额最少硬币个数 = min（当前总金额-某硬币面值）+ 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                if (i - coins[j] >= 0)
                {
                    dp[i] = min(dp[i], dp[i-coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

单词拆分

Problem

https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked

Solution

某字符串能拆成单词组合的条件是尾部刚好是一个wordDict里的单词，且去除这个单词后的字符串能拆成单词组合。

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
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len = s.size();
        vector<bool> dp(len+1, false);
        dp[0] = true;
        for (int end = 1; end <= len; end ++)
        {
            for (int i = 0; i < wordDict.size(); i ++)
            {
                const string &word = wordDict[i];

                if (word.length() <= end)
                {
                    string sub_str = s.substr(end-word.length(), word.length());
                    if (sub_str == word && dp[end-word.length()])
                    {
                        dp[end] = true;
                    }
                }
            }
        }

        return dp[len];
    }
};

最长递增子序列

Problem

https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-100-liked

Solution

整个数组中最长严格递增子序列的长度=以每个数为结尾的严格递增子序列长度中的最大值，以某个数为结尾的严格递增子序列长度=max（以前面某个小于当前数的数为结尾的长度）+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 lengthOfLIS(vector<int>& nums) {
        int n = nums.size();

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

乘积最大子数组

Problem

https://leetcode.cn/problems/maximum-product-subarray/?envType=study-plan-v2&envId=top-100-liked

Solution

数组中乘积最大的非空连续子数组=以每个数为结尾的乘积最大非空连续子数组中的乘积最大者；考虑到负数的存在，以某个数为结尾的合法数组=max（当前数x前面的最小值，当前数x前面的最大值，当前数），由于是连续的，所以只考虑前一项即可。
多了几个奇葩样例，开long long都过不了。

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

        long long ans = nums[0];
        for (int i = 0; i < n; i ++)
        {
            long long cur_max_product = max(max(nums[i] * max_product, nums[i] * min_product), (long long)nums[i]);
            long long cur_min_product = min(min(nums[i] * max_product, nums[i] * min_product), (long long)nums[i]);
            ans = max(ans, cur_max_product);
            max_product = cur_max_product;
            min_product = cur_min_product;
        }
        return ans;
    }
};

分割等和子集

Problem

https://leetcode.cn/problems/partition-equal-subset-sum/?envType=study-plan-v2&envId=top-100-liked

Solution

分割等和子集，相当于从数组中选数，使和等于总和的一半。转换为背包问题，每个数只能选一次，且总和要刚好等于目标值。

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
37
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        int n = nums.size();
        for (int i = 0; i < n; i ++)
        {
            sum += nums[i];
        }

        if (sum & 1) return false;

        int target_num = sum >> 1;

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

        for (int j = 0; j < n; j ++)
        {
            dp[0][j] = true;
        }
        for (int i = 1; i <= target_num; i ++)
        {
            for (int j = 1; j < n; j ++)
            {
                if (i - nums[j] >= 0)
                {
                    dp[i][j] = dp[i-nums[j]][j-1] | dp[i][j-1];
                }
                else
                {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[target_num][n-1];
    }
};

最长有效括号

Problem

https://leetcode.cn/problems/longest-valid-parentheses/?envType=study-plan-v2&envId=top-100-liked

Solution

字符串中合法最长子串的长度=以每个字符为结尾的合法子串长度中的最大值。dp[i]代表以第i个字符为结尾的合法子串的长度，当前右括号和某左括号配对时，还需要把这个左括号前面的长度考虑进来，具体状态转移方程见代码。

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:
    int longestValidParentheses(string s) {

        int n = s.size();
        if (n == 0) return 0;
        vector<int> dp(n, 0);
        dp[0] = 0;
        int ans = 0;
        for (int i = 1; i < n; i ++)
        {
            if (s[i] == '(')
            {
                dp[i] = 0;
            }
            else if (s[i-1] == '(')
            {
                dp[i] = (i-2 >= 0 ? dp[i-2] + 2 : 2);
            }
            else if (s[i-1] == ')' && (i - dp[i-1] - 1) >= 0 && s[i - dp[i-1] - 1] == '(')
            {
                if (i - dp[i-1] - 2 >= 0 && s[i - dp[i-1] - 2] == ')')
                {

                    dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] - 2];
                }
                else
                {
                    dp[i] = 2 + dp[i-1];
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

不同路径

Problem

https://leetcode.cn/problems/unique-paths/?envType=study-plan-v2&envId=top-100-liked

Solution

dp[i][j] = dp[i-1][j] + dp[i][j-1]，边界为1，可以压缩成1维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int uniquePaths(int m, int n) {

        vector<int> dp(n, 1);

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

最小路径和

Problem

https://leetcode.cn/problems/minimum-path-sum/?envType=study-plan-v2&envId=top-100-liked

Solution

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

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
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dp(n, 0);

        dp[0] = grid[0][0];

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

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

最长回文字串

Problem

https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked

Solution

从小到大枚举字串长度，初始dp全为true，dp[i][j]代表[i, j]的子串是否为回文串，dp[i][j]=dp[i+1][j-1] && s[i] == s[j]

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
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, true));

        int max_start = 0;
        int max_len = 1;
        for (int len = 2; len <= n; len ++)
        {
            for (int start = 0; start <= n - len; start ++)
            {
                int end = start + len - 1;

                dp[start][end] = dp[start+1][end-1] && s[start] == s[end];

                if (dp[start][end])
                {
                    max_start = start;
                    max_len = len;
                }
            }
        }
        return s.substr(max_start, max_len);
    }
};

最长公共子序列

Problem

https://leetcode.cn/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=top-100-liked

Solution

令dp[i][j]代表text1[0:i],text2[0:j]最长公共子序列长度。

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
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.length();
        int len2 = text2.length();

        vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));

        for (int i = 0; i < len1; i ++)
        {
            for (int j = 0; j < len2; j ++)
            {
                if (text1[i] == text2[j])
                {
                    dp[i+1][j+1] = max(max(dp[i][j] + 1, dp[i+1][j]), dp[i][j+1]);
                }
                else
                {
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        return dp[len1][len2];

    }
};

编辑距离

Problem

https://leetcode.cn/problems/edit-distance/?envType=study-plan-v2&envId=top-100-liked

Solution

dp[i][j]代表从word1[0:i]变换到word2[0:j]所需的最少操作数。

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
class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();

        vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));

        for (int i = 0; i <= len1; i ++)
        {
            dp[i][0] = i;
        }

        for (int j = 0; j <= len2; j ++)
        {
            dp[0][j] = j;
        }

        for (int i = 1; i <= len1; i ++)
        {
            for (int j = 1; j <= len2; j ++)
            {
                int insert1 = dp[i][j-1] + 1;
                int insert2 = dp[i-1][j] + 1;
                int replace = dp[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0 : 1);

                dp[i][j] = min(min(insert1, insert2), replace);
            }
        }
        return dp[len1][len2];
    }
};