单调栈：通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。   单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素（如果遇到更小的就先存着，并不断动态处理栈顶，栈顶解决了再往回回退处理），优点是整个数组只需要遍历一次。    739. 每日温度 暴力超时。 class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { vector&lt...

647. 回文子串 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; } } } }  516.最长回文子序列 class Solution { public: int...

583. 两个字符串的删除操作 class Solution { public: int minDistance(string word1, string word2) { vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1)); 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...

392.判断子序列 class Solution { public: bool isSubsequence(string s, string t) { vector<vector<int>> dp(s.size() + 1, vector<int>(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] + ...

1143.最长公共子序列 class Solution { public: int longestCommonSubsequence(string text1, string text2) { vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0)); for (int i = 1; i <= text1.size(); i++) { for (int j = 1; j <= text2.size(); j++) { if (text1[i - 1] ==...

300.最长递增子序列 class Solution { public: int lengthOfLIS(vector<int>& nums) { if (nums.size() <= 1) return nums.size(); vector<int> dp(nums.size(), 1); int result = 0; for (int i = 1; i < nums.size(); i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) dp[i] = max(dp[...

300.最长递增子序列 class Solution { public: int lengthOfLIS(vector<int>& nums) { if (nums.size() <= 1) return nums.size(); vector<int> dp(nums.size(), 1); int result = 0; for (int i = 1; i < nums.size(); i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) dp[i] = max(dp[...

123.买卖股票的最佳时机III class Solution { public: int maxProfit(vector<int>& prices) { if (prices.size() == 0) return 0; vector<vector<int>> dp(prices.size(), vector<int>(5, 0)); dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for (int i = 1; i < prices.size(); i++) { dp[i][0] =...

121. 买卖股票的最佳时机 class Solution { public: int maxProfit(vector<int>& prices) { int len = prices.size(); if (len == 0) return 0; vector<vector<int>> dp(len, vector<int>(2)); dp[0][0] -= prices[0]; dp[0][1] = 0; for (int i = 1; i < len; i++) { dp[i][0] = max(dp[i - 1][0], ...

198.打家劫舍 class Solution { public: int rob(vector<int>& nums) { if (nums.size() == 0) return 0; if (nums.size() == 1) return nums[0]; vector<int> 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]...

139.单词拆分 class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); vector<bool> dp(s.size() + 1, false); dp[0] = true; for (int i = 1; i <= s.size(); i++) { // 遍历背包 for (int j = 0; j < i;...

70. 爬楼梯 （进阶） 每一步可以走1~m步，转化成完全背包。 class Solution { public: int climbStairs(int n) { vector<int> dp(n + 1, 0); dp[0] = 1; m = 2; for (int i = 1; i <= n; i++) { // 遍历背包 for (int j = 1; j <= m; j++) { // 遍历物品 if (i - j >= 0) dp[i] += dp[i - j]; } } return dp[n]; } };  322. 零钱兑换 class Solu...

完全背包 完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。 j内层为顺序遍历，因为一个物品可以取多次，同时先物品还是先容量遍历都可以，dp之前的数值都已经计算过。 518. 零钱兑换 II 满背包一刷过。 377. 组合总和 Ⅳ 满背包一刷过。

1049. 最后一块石头的重量 II 和分割等和子集一样，转化成分成两堆尽量相等的石碓，也就是尽可能装满Sum/2。 class Solution { public: int lastStoneWeightII(vector<int>& stones) { vector<int> dp(1501, 0); int sum = 0; for (int i = 0; i < stones.size(); i++) { sum += stones[i]; } int target = sum / 2; for (int i = 0; i < stones....