九、动态规划

步骤：

1.确定dp数组的下标及其含义

2.确定递推公式

3.dp数组初始化

4.确定遍历顺序

5.举例推导

1.斐波那契数（509）

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

2.爬楼梯（70）

class Solution {
public:int climbStairs(int n) {if (n == 1) return 1;vector dp(n + 1);dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];return dp[n];}
};// 完全背包
/*
class Solution {
public:int climbStairs(int n) {vector dp(n + 1, 0);dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= 2; j++) {if (i >= j) dp[i] += dp[i - j];}}return dp[n];}  
};
*/

3.使用最小花费爬楼梯（746）

class Solution {
public:int minCostClimbingStairs(vector& cost) {if (cost.size() == 2) return min(cost[0], cost[1]);vector dp(cost.size() + 1);dp[1] = 0;dp[2] = min(cost[0], cost[1]);for (int i = 3; i <= cost.size(); i++) dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);return dp[cost.size()]; }
};

4.不同路径（62）

class Solution {
public:int uniquePaths(int m, int n) {vector> dp(m, vector(n, 0));for (int i = 0; i < m; i++) dp[i][0] = 1;for (int j = 0; j < n; j++) dp[0][j] = 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];}
};

5.不同路径II（63）

class Solution {
public:int uniquePathsWithObstacles(vector>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;vector> dp(m, vector(n, 0));for (int i = 0; i < m; i++) {if (obstacleGrid[i][0] == 1) break;dp[i][0] = 1;}for (int j = 0; j < n; j++) {if (obstacleGrid[0][j] == 1) break;dp[0][j] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) dp[i][j] = 0;else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};

6.整数拆分（343）

class Solution {
public:int integerBreak(int n) {vector dp(n + 1, 0);dp[2] = 1;for (int i = 3; i <= n; i++) {for (int j = 1; j < i - 1; j++) {dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));}}return dp[n];}
};

7.不同的二叉搜索树（96）

class Solution {
public:int numTrees(int n) {vector dp(n + 1, 0);dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
};

8.分割等和子集（416）

class Solution {
public:bool canPartition(vector& nums) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (sum % 2 == 1) return false;int target = sum / 2;vector dp(10001, 0);for (int i = 0; i < nums.size(); i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}if (dp[target] == target) return true;return false;}
};

9.最后一块石头的重量 II（1049）

class Solution {
public:int lastStoneWeightII(vector& stones) {int sum = 0;for (int i = 0; i < stones.size(); i++) sum += stones[i];int target = sum / 2;vector dp(1501, 0);for (int i = 0; i < stones.size(); i++) {for (int j = target; j >= stones[i]; j--) {dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] - dp[target];}
};

10.目标和（494）

class Solution {
public:int findTargetSumWays(vector& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if ((sum + target) % 2 == 1) return 0;if (abs(target) > sum) return 0;int bagSize = (sum + target) / 2;if (bagSize < 0) return 0;vector dp(bagSize + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
};

11.一和零（474）

class Solution {
public:int findMaxForm(vector& strs, int m, int n) {vector> dp(m + 1, vector(n + 1, 0));for (string str : strs) {int zeroNum = 0, oneNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) {for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};

01背包中二维dp数组的两个for遍历的先后循序是可以颠倒；

01背包中一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量，且内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次

完全背包中一维dp数组，其实两个for循环嵌套顺序是可以颠倒的，而完全背包的物品是可以添加多次的，所以内循环要从小到大去遍历

总之，01背包用一维dp先从小到大遍历物品，再从大到小遍历背包；完全背包用一维dp可以先从小到大遍历物品，再从小到大遍历背包，也可以先从小到大遍历背包，再从小到大遍历物品，取决于具体题目，如果求组合数就是外层遍历物品内层遍历背包，求排列数就是外层遍历背包内层遍历物品

12.零钱兑换 II（58）

class Solution {
public:int change(int amount, vector& coins) {vector dp(amount + 1, 0);dp[0] = 1;for (int i = 0; i < coins.size(); i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

13.组合总和 IV（377）

class Solution {
public:int combinationSum4(vector& nums, int target) {vector dp(target + 1, 0);dp[0] = 1;for (int j = 0; j <= target; j++) {for (int i = 0; i < nums.size(); i++) {if (j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]]) dp[j] += dp[j - nums[i]];}}return dp[target];}
};

14.完全平方数（279）

class Solution {
public:int numSquares(int n) {vector dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i * i <= n; i++) {for (int j = 1; j <= n; j++) {if (j >= i * i) {dp[j] = min(dp[j], dp[j - i * i] + 1);}}}return dp[n];}
};

15.单词拆分（139）

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

16.打家劫舍（198）

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

17.打家劫舍 II（213）

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

18.打家劫舍 III（337）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector robTree(TreeNode* cur) {if (cur == NULL) return vector{0, 0};vector left = robTree(cur->left);vector right = robTree(cur->right);int val1 = cur->val + left[0] + right[0];int val2 = max(left[0], left[1]) + max(right[0], right[1]);return vector{val2, val1};}int rob(TreeNode* root) {vector res = robTree(root);return max(res[0], res[1]);}
};

19.买卖股票的最佳时机（121）

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

20.买卖股票的最佳时机 II（122）

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

21.买卖股票的最佳时机 III（123）

class Solution {
public:int maxProfit(vector& prices) {if (prices.size() == 1) return 0;vector> dp(prices.size(), vector(5, 0));dp[0][1] = -prices[0];dp[0][3] = -prices[0];for (int i = 1; i < prices.size(); i++) {dp[i][0] = dp[i - 1][0];dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}return dp[prices.size() - 1][4];}
};

22.买卖股票的最佳时机 IV（188）

class Solution {
public:int maxProfit(int k, vector& prices) {if (prices.size() == 1) return 0;vector> dp(prices.size(), vector(2 * k + 1, 0));for (int j = 1; j < 2 * k + 1; j += 2) dp[0][j] = -prices[0];for (int i = 1; i < prices.size(); i++) {for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);}}return dp[prices.size() - 1][2 * k];}
};

23.最佳买卖股票时机含冷冻期（309）

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

24.买卖股票的最佳时机含手续费（714）

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

25.最长递增子序列（300）

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

26.最长连续递增序列（674）

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

27.最长重复子序列（718）

class Solution {
public:int findLength(vector& nums1, vector& nums2) {vector> dp(nums1.size() + 1, vector(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > result) result = dp[i][j];}}return result;}
};

28.最长公共子序列（1143）

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector> dp(text1.size() + 1, vector(text2.size() + 1, 0));for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); 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[text1.size()][text2.size()];}
};

29.不相交的线（1035）

class Solution {
public:int maxUncrossedLines(vector& nums1, vector& nums2) {vector> dp(nums1.size() + 1, vector(nums2.size() + 1, 0));for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[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[nums1.size()][nums2.size()];}
};

30.最大子数组和（53）

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

31.判断子序列（392）

class Solution {
public:bool isSubsequence(string s, string t) {vector> dp(s.size() + 1, vector(t.size() + 1, 0));for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}if (dp[s.size()][t.size()] == s.size()) return true;else return false;}
};

32.不同的子序列（115）

class Solution {
public:int numDistinct(string s, string t) {vector> dp(s.size() + 1, vector(t.size() + 1, 0));for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];else dp[i][j] = dp[i - 1][j];}}return dp[s.size()][t.size()];}
};

33.两个字符串的删除操作（583）

class Solution {
public:int minDistance(string word1, string word2) {vector> dp(word1.size() + 1, vector(word2.size() + 1, 0));for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); 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], dp[i][j - 1]) + 1;}}return dp[word1.size()][word2.size()];}
};

34.编辑距离（72）

class Solution {
public:int minDistance(string word1, string word2) {vector> dp(word1.size() + 1, vector(word2.size() + 1, 0));for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;for (int i = 1; i <= word1.size(); i++) {for (int j = 1; j <= word2.size(); 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;}}return dp[word1.size()][word2.size()];}
};

35.回文子串（647）

class Solution {
public:int countSubstrings(string s) {vector> dp(s.size(), vector(s.size(), false));int result = 0;for (int i = s.size() - 1; i >= 0; i--) {for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) {result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) {result++;dp[i][j] = true;}}}}return result;}
};

36.最长回文子串（516）

class Solution {
public:int longestPalindromeSubseq(string s) {vector> dp(s.size(), vector(s.size(), 0));for (int i = 0; i < s.size(); i++) dp[i][i] = 1;for (int i = s.size() - 1; i >= 0; i--) {for (int j = i + 1; j < s.size(); 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][s.size() - 1];}
};

十、单调栈

1.每日温度（739）

class Solution {
public:vector dailyTemperatures(vector& temperatures) {stack st;vector result(temperatures.size(), 0);st.push(0);for (int i = 1; i < temperatures.size(); i++) {if (temperatures[i] <= temperatures[st.top()]) st.push(i);else {while (!st.empty() && temperatures[i] > temperatures[st.top()]) {result[st.top()] = i - st.top();st.pop();}st.push(i);}}return result;}
};

2.下一个更大元素 I（496）

class Solution {
public:vector nextGreaterElement(vector& nums1, vector& nums2) { vector result(nums1.size(), -1);unordered_map umap;for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}stack st;st.push(0);for (int i = 1; i < nums2.size(); i++) {if (nums2[st.top()] >= nums2[i]) st.push(i);else {while (!st.empty() && nums2[st.top()] < nums2[i]) {if (umap.find(nums2[st.top()]) != umap.end()) {int idx = umap[nums2[st.top()]];result[idx] = nums2[i];  }st.pop();}st.push(i);}}return result;}
};

3.下一个更大元素 II（503）

class Solution {
public:vector nextGreaterElements(vector& nums) {vector nums0(nums.begin(), nums.end());nums.insert(nums.end(), nums0.begin(), nums0.end());vector result(nums.size(), -1);stack st;st.push(0);for (int i = 1; i < nums.size(); i++) {while (!st.empty() && nums[st.top()] < nums[i]) {result[st.top()] = nums[i];st.pop();}st.push(i);}result.resize(nums.size() / 2);return result;}
};

4.接雨水（42）

class Solution {
public:int trap(vector& height) {if (height.size() <= 2) return 0;int sum = 0;stack st;st.push(0);for (int i = 1; i < height.size(); i++) {if (height[i] < height[st.top()]) {st.push(i);} else if (height[i] == height[st.top()]) {st.pop();st.push(i);} else {while (!st.empty() && height[i] > height[st.top()]) {int mid = height[st.top()];st.pop();if (!st.empty()) {int h = min(height[st.top()], height[i]) - mid;int w = i - st.top() - 1;sum += h * w;}  }st.push(i);}}return sum;}
};

5.柱状图中最大的矩形（84）

class Solution {
public:int largestRectangleArea(vector& heights) {heights.insert(heights.begin(), 0);heights.push_back(0);stack st;st.push(0);int result = 0;for (int i = 1; i < heights.size(); i++) {if (heights[i] > heights[st.top()]) {st.push(i);} else if (heights[i] == heights[st.top()]) {st.pop();st.push(i);} else {while (!st.empty() && heights[i] < heights[st.top()]) {int mid = heights[st.top()];st.pop();if (!st.empty()) {int h = mid;int w = i - st.top() - 1;result = max(result, h * w);}}st.push(i);}}return result;}
};