LeetCode中动态规划题解合集（根据难易程度））

106 阅读 0 评论 70 点赞

我是靠谱客的博主无奈日记本，这篇文章主要介绍LeetCode中动态规划题解合集（根据难易程度）），现在分享给大家，希望可以做个参考。

121.Best Time to Buy and Sell Stock
思路：遍历数组，找到当前位置之前最小的数，然后选择当前买入差值和之前最大值之间的最大值。

复制代码

1
2
3
4
5
6
7
8
9
 int maxProfit(vector<int>& prices) {
        int res = 0,buy = INT_MAX;
        for (int price : prices) {
            buy = min(buy,price);
            res = max(res,price - buy);
        }
        return res;
    }

746.Min Cost Climbing Stairs
思路：从第二个台阶开始，计算到达该台阶最小的cost，因为第i个台阶，和i-1和i-2有关，则计算cost[i]

min(cost[i-1],cost[i-2]).

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
 int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n,0);
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + min(dp[i-1],dp[i-2]);
        }
        
        return min(dp[n-1],dp[n-2]);
    }

思路2：因为我们只关注i-1和i-2的值，所以没必要保存所有台阶的值，只需要保存i-1和i-2.

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int a = cost[0];
        int b = cost[1];
        int t;
        for (int i = 2; i < n; i++) {
            t = cost[i] + min(a,b);
            a = b;
            b = t;
        }
        return min(t,a);
    }

Climbing Stairs
思路：第i层台阶，只和第i-1和i-2层台阶有关系，那么从底3层台阶开始，第i层台阶组合 = i-1层台阶组合数 + i-2层台阶组合数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int climbStairs(int n) {
        int a = 1,b = 2;
        int res = 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        for (int i = 3; i <= n; i++) {
            res = a + b;
            a = b;
            b = res;
        }
        return res;
    }

Maximum Subarray
思路：最大连续子数组，curSum初始值为0，每遍历一个数字num，比较curSum + num和num中的较大值存入curSum，然后再把res和curSum中的较大值存入res，以此类推直到遍历完整个数组，可得到最大子数组的值存在res中。原理，如果前面的和是负数，那么就没有必要相加，每次元素累加和小于0时，从下一个元素重新开始累加。

复制代码

1
2
3
4
5
6
7
8
9
10
int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int curSum = 0;
        for (int num : nums) {
            curSum = max(num,curSum + num);//换句话就是，如果cursum为负，那么最大值就是num
            res = max(curSum,res);
        }
        return res;
    }

House Robber
思路：递推公式dp[i] = max(num[i] + dp[i - 2], dp[i - 1]), 由此看出我们需要初始化dp[0]和dp[1]，其中dp[0]即为num[0]，dp[1]此时应该为max(num[0], num[1])。但是我们只需要前两个值，所以不需要保存所有dp的值，所以用a,b局部变量。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 int rob(vector<int>& nums) {
        if (nums.size() <= 1) return nums.empty() ? 0 : nums[0];
        if (nums.size() == 2) return max(nums[0],nums[1]);
        int a = nums[0];
        int b = max(a,nums[1]);
        int res = 0;
        for (int i = 2; i < nums.size(); i++) {
            res = max(a + nums[i],b);
            a = b;
            b = res;
        }
        return max(res,a);
    }

Range Sum Query - Immutable
思路：如果直接遍历求和的话，无法通过，所以用dp来记录[0,j]的和，如果求[i,j]的区间和，就用dp[j]-dp[i].

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public:
    NumArray(vector<int> nums) {
        dp.resize(nums.size()+1,0);
        for (int i = 1;i < nums.size() + 1; i++) {
            dp[i] = dp[i-1] + nums[i-1];
        }
    }
    
    int sumRange(int i, int j) {
        return dp[j+1] - dp[i];
    }
private:
    vector<int> dp;

Palindromic Substrings
思路：helper函数用来计算以s[i]为中心的回文字符串个数，又因为回文数可能是单数也可能是双数，所以中心可能是一个数s[i],也可能是s[i]和s[i+1]，所以需要helper(s,i,i,res);和helper(s,i,i+1,res);两个计算。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int countSubstrings(string s) {
        int res = 0;
        for(int i = 0; i < s.size();i++) {
            helper(s,i,i,res);
            helper(s,i,i+1,res);
        }
        return res;
    }
    void helper(string s,int i,int j,int &res) {
        while (i >= 0 && j < s.size()) {
            if (s[i] != s[j])
                break;
            i--,j++;
            res++;
        }
    }

思路2：dp[i][j]定义成子字符串[i,j]是否为回文串，i从n-1开始向前遍历，j也从n-1向前遍历直到j == i,如果i ==j,那么[i,j]是回文串，如果i,j相邻或者中间隔一个数，那么比较s[i] == s[j]?如果相等，则是回文串，如果i和j中间隔大于一个数，那么判断dp[i+1][j-1]是否为真，若为真，则是回文串。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countSubstrings(string s) {
        int n = s.size();
        int res = 0;
        vector<vector<bool>> dp(n,vector<bool>(n,false));
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j >= i; j--) {
                if (s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1]))
                    dp[i][j] = true;
                if (dp[i][j]) res++;
            }
        }
        return res;
    }

Arithmetic Slices
思路：求等差数列的个数。定义dp[i]为以A[i]为结尾的数列中等差数列的个数，那么dp[i] = dp[i-1] + 1;res每次加上dp[i]即可

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        int res = 0;
        vector<int> dp(n,0);
        for (int i = 2; i < n; i++) {
            if (A[i] - A[i-1] == A[i-1] - A[i-2])
                dp[i] = dp[i-1] + 1;
            res += dp[i];
        }
        return res;
    }

思路2：可以不保存所有dp值，用一个变量代替就可。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        int res = 0;
        int old = 0,cur = 0;
        for (int i = 2; i < n; i++) {
            if (A[i] - A[i-1] == A[i-1] - A[i-2]) {
                cur = old + 1;
                old = cur;
            }
            else {
                old = 0;
                cur = 0;
            }
            res += cur;
        }
        return res;
    }

Minimum ASCII Delete Sum for Two Strings
思路：dp[i][j]表示s1中前i个字符和s2前j个字符中，删除的最小字符和。初始化dp[i][0]和dp[0][j].当s1[i] == s2[j-1]时，那么不需要删除字符，所以dp[i][j] == dp[i-1][j-1],当s1[i] != s2[j]时，那么比较dp[i-1][j] + s1[i-1]和dp[i][j-1] + s2[j-1]大小，选择删除s1[i-1]或者s2[j-1].

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minimumDeleteSum(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for (int i = 1; i <= m; i++)
            dp[i][0] = dp[i-1][0] + s1[i-1];
        for (int j = 1; j <= n; j++) 
            dp[0][j] = dp[0][j-1] + s2[j-1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = s1[i-1] == s2[j-1] ? dp[i-1][j-1] : 
                min(dp[i-1][j] + s1[i-1],dp[i][j-1] + s2[j-1]);
            }
        }
        return dp[m][n];
    }

Maximum Length of Pair Chain
思路：首先，把pairs进行排序，排序算法根据vecSort函数，pair中尾元素进行排序（这里为什么不用首元素进行排序呢），也就是a[1] < b[1],然后根据贪心算法，用一个变量end来记录当前比较到的尾元素的值，初始化为最小值，然后遍历的时候，如果当前链对的首元素大于end，那么结果res自增1，end更新为当前链对的尾元素。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 static bool vecSort( vector<int> &a, vector<int> &b) {
        return a[1] < b[1];
    }
    
    int findLongestChain(vector<vector<int>>& pairs) {
        int res = 0,end = INT_MIN;
        sort(pairs.begin(),pairs.end(),vecSort);
        for (auto pair : pairs) {
            if (pair[0] > end) {
                res++;
                end = pair[1];
            }
        }
        return res;
    }

Integer Break
思路：dp[i]表示整数i分解后最大乘积，那么维护这个dp数组,i被分成两个数的和或者多个数的和。对于两个数的和，就是用j * (i-j),多个数的和，就需要前面已经计算过的dp[j] *(i-j),最后比较。

但是这样复杂度就是O(n^2),不是之前要求的O(n).O(n)的话需要找数学规律。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
int integerBreak(int n) {
        vector<int> dp(n+1,1);
        int t;
        for (int i = 2; i <= n; i ++) {
            for (int j = 1; j < i; j++) {
                t = max(j * (i-j),dp[j] * (i - j));
                dp[i] = max(t,dp[i]);
            }
        }
        return dp[n];
    }

Count Numbers with Unique Digits
思路：一位数的时候，满足要求的是10位数，两位数的时候，第一位可选数字为9，第二位可选数字也是9，那么两位数满足要求数字是99，三位数满足要求是998…以此类推。dp[i]表示i位数时满足要求数字，初始化dp[0] = 1(这里不是0，是为了后面递推式dp[i] = dp[i-1] + (dp[i-1] - dp[i-2]) (9 - i + 2);从2满足），然后dp[1] = 10，然后递推式dp[i] = dp[i-1] + (dp[i-1] - dp[i-2])* (9 - i + 2);，i位数满足要求的数字是小于等于i-1位数满足要求的数字加上只有i位数满足要求的数的和。

复制代码

1
2
3
4
5
6
7
8
9
int countNumbersWithUniqueDigits(int n) {
        vector<int> dp(n+1,1);
        dp[1] = 10;
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i-1] + (dp[i-1] - dp[i-2])* (9 - i + 2);
        }
        return dp[n];
    }

2 Keys Keyboard
思路：找到n 的因子j，然后这个因子j当作copy模板，我们再算出paste这个模板要多少次i/j.dp[i]表示i个A需要的操作数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int minSteps(int n) {
        vector<int> dp(n+1,0);
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    dp[i] = min(dp[i],dp[j] + i / j);
                }
            }
           
        }
        return dp[n];
    }

Predict the Winner
思路：搜索答案说的最多的就是Minimax算法。这个算法很适合用于这种交替型的博弈问题，对手双方的策略都是一样的，每次都选择最优解，所以运用到了区间dp[i][j]表示在区间i和j，可以获得的最大值。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
        }
        for (int len = 1; len < n; len++) {
            for (int i = 0,j = len; j < n; i++,j++) {
                dp[i][j] = max(nums[i] - dp[i+1][j],nums[j] - dp[i][j-1]);
            }
        }
        return dp[0][n-1]>=0;
    }

Is Subsequence
思路：i和j相当于s和t的指针，如果s[i]和t[j]相等，那么i++,j++,都向下移动一位，如果不相等，那么只有t向下移动一位（j++),最后判断i是不是等于s的长度。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 bool isSubsequence(string s, string t) {
        int m = s.size();
        int n = t.size();
        int i = 0,j = 0;
        while (i < m && j < n) {
            if (s[i] == t[j]) {
                i++;
                j++;
            }
            else {
                j++;
            }
        }
        if (i == m) {
            return true;
        }
        return false;
    }

Unique Paths
思路：dp[i][j]表示第i行j列的所有路径数，因为robot只能下移或者右移，所以i,j的路径只能是[i-1][j]位置的路径 + [i][j-1]位置的路径。

复制代码

1
2
3
4
5
6
7
8
9
10
11
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];
    }

Delete and Earn
思路：首先明确一点，选择某一个数字，那么这个数字不管有几个，我们都会加入最后的和当中，所以我们先统计每个数字有几个，用cnt数组保存。然后dp[i]表示到i为止最大值，dp[i]有两个选择，要么选择拿i这个数，cnt[i] * i + dp[i-2],要么不拿i这个数，dp[i-1],最后返回dp[10000]

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(10001,0);
        
        vector<int> cnt(10001,0);
        for(int i = 0; i < n; i++)
            cnt[nums[i]]++;
        dp[1] = cnt[1];
        for (int i = 2; i < 10001; i++) {
            dp[i] = max(dp[i-2] + cnt[i] * i,dp[i-1]);
        }
        return dp[10000];
        
    }

Target Sum
思路：这第一个想到的是DFS，列出来所有情况，判断和是否为S。所以最简单就是用DFS，对目标值每次减去或者加上当前数字，最后得到的值是否为0判断是否满足要求。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 int findTargetSumWays(vector<int>& nums, int S) {
        int res = 0;
        helper(nums,S,0,res);
        return res;
    }
    void helper(vector<int>& nums,int S,int start,int& res) {
        if (start >= nums.size()) {
            if (S == 0)
                res++;
            return;
        }
        
        helper(nums,S-nums[start],start+1,res);
        helper(nums,S+nums[start],start+1,res);
    }

Longest Palindromic Subsequence
思路：找最大子序列，可以不连续（和最长子字符串不同）。dp[i][j]表示从i到j的最长回文字符串，如果s[i] == s[j],那么dp[i][j] = dp[i+1][j-1] + 2;如果不相等，那么 dp[i][j] = max(dp[i+1][j],dp[i][j-1]);

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j])
                    dp[i][j] = dp[i+1][j-1] + 2;
                else {
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }

Unique Binary Search Trees
思路：二叉搜索树，对于根节点root来说，左边的一定小于root，右边的大于root，所以如果给定一个数n，说明n个数进行BST，那么左子树节点个数为k（0<=k<=n-1),右子树节点个数为n-k-1;dp[i]表示i个数BST的可能构造数，那么dp[n] += dp[k] * dp[n-k-1] (0<=k<=n-1).最后返回dp[n]就是结果。

复制代码

1
2
3
4
5
6
7
8
9
10
11
 int numTrees(int n) {
        vector<int> dp(n+1,0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }

64.Minimum Path Sum
思路：dp[i][j]表示i行j列最小路径和，因为只能向右和向下移动，所以dp[i][j] = min (dp[i-1][j],dp[i][j-1]) + grid[i][j];也就是说，dp[i][j]只能来自于它上面的块和左边的块，所以比较这两个大小，取其小的那一块就可以。代码中需要先初始化第一行和第一列dp值。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dp = grid;
        for (int i = 1; i < n; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        
        for (int i = 1; i < n; i ++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = min (dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[n-1][m-1];
    }

377.Combination Sum IV
思路：第一想法是DFS，但是超时，所以还是用DP。dp[i] 表示和为i时，组合数，那么dp[i] = dp[i-nums[0] ] + dp[i - nums[1]] + …dp[i - nums[size-1]].用代码表示就是dp[i] += dp[i - num];

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(target+1,0);
        dp[0] = 1;
        sort(nums.begin(),nums.end());
        for(int i = 1; i <= target; i++) {
            for (auto num : nums) {
                if (num <= i)
                    dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }

Maximum Length of Repeated Subarray
思路：dp[i][j]表示数组A中前i个字符和数组B前j个字符最长公共子数组的个数，如果A[i] == B[j]，那么dp[i][j]等于dp[i-1][j-1] + 1,最后找到dp中最大值即可。其中有个小技巧，因为是从0开始计算，但是i-1和j-1不能是负数，所以i,j从1计数，但是比较还是i-1,j-1,相当于还是0，只是保存结果从[1][1]开始的。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findLength(vector<int>& A, vector<int>& B) {
        int m = A.size();
        int n = B.size();
        int res = 0;
        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 (A[i-1] == B[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res,dp[i][j]);
                }
            }
        }
        return res;
    }

72`edit distance
思路：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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));
        int dp[m+1][n+1];
        for (int i = 0; i < m + 1; i++) 
            dp[i][0] = i;
        for (int i = 0; i < n + 1; i++)
            dp[0][i] = i;
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                }
                else {
                    dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1])) + 1;//这里一定要注意，min函数只接受两个参数，必须写两个min
                }
            }
        }
        return dp[m][n];
    }