算法汇总整理篇——贪心与动态规划学习及框架思考

算法的知识储备

动态规划算法(重中之重)

如果某⼀问题有很多重叠⼦问题，使⽤动态规划是最有效的
动规是由前⼀个状态推导出来的，⽽贪⼼是局部直接选最优的

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序

5. 举例推导dp数组

不同路径II

dp[i][j] 表示到达位置ij共有多少中方法

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();//如果在起点或终点出现了障碍，直接返回0if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) return 0;vector<vector<int>> dp(m, vector<int>(n));  for(int i = 0; i< m && obstacleGrid[i][0] == 0; i++){  //在循环条件里判断dp[i][0] = 1;}for(int i = 0; i< n && obstacleGrid[0][i] == 0; i++){dp[0][i] = 1;}for(int i = 1; i < m; i++){for(int j =1; j < n; j++){if(obstacleGrid[i][j] != 1)dp[i][j] = dp[i-1][j] + dp[i][j-1];if(obstacleGrid[i][j] == 1)continue;}}return dp[m-1][n-1];}
};

整数拆分

dp[i] 表示拆分数字i的乘积最大值

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);  dp[0] = 0;dp[1] = 1;for(int i = 2; i <= n; i++){for(int j = 1; j < i; j++){dp[i] = max(dp[i], max((i-j)*j, dp[i-j] * j)); //j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘}}return dp[n];}
};

不同的二叉搜索树

dp[n] n个节点组成的节点值从1到n互不相同的二叉搜索树数量

dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

num i, root j : left j-1 right i-j j相当于是头结点的元素，从1遍历到i为止。

j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1);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];}
};

背包问题

(理清楚物品和背包，递推公式为背包容量项！！！！！)

01背包

dp[i][j]代表背包容量为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值

递推公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

递推公式： dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

#include <bits/stdc++.h>
using namespace std;int main() {int n, bagweight;         // bagweight代表行背包容量cin >> n >> bagweight;vector<int> weight(n, 0); // 存储每件物品所占容量vector<int> value(n, 0);  // 存储每件物品价值for(int i = 0; i < n; ++i) {cin >> weight[i];}for(int j = 0; j < n; ++j) {cin >> value[j];}vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化, 因为需要用到dp[i - 1]的值// j < weight[0]已在上方被初始化为0// j >= weight[0]的值就初始化为value[0]for (int j = weight[0]; bagweight - j >= 0; j++) {dp[0][j] = value[0];}for(int i = 1; i < weight.size(); i++) {     // 遍历物品类型for(int j = 0; j <= bagweight; j++) {    // 遍历背包容量if (j - weight[i] < 0) dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}cout << dp[n - 1][bagweight] << endl;return 0;
}

一维dp 滚动数组

一维dp的写法，背包容量一定是要倒序遍历；防止重复添加 (先物品类型后背包容量)

通过物品判断可否装入

#include <iostream>
#include <vector>
using namespace std;int main() {int num, weights;cin >> num >> weights;vector<int> costs(num);vector<int> values(num);for (int i = 0; i < num; i++) {cin >> costs[i];}for (int j = 0; j < num; j++) {cin >> values[j];}// 创建一个动态规划数组dp，初始值为0vector<int> dp(weights + 1, 0);// 外层循环遍历每个类型的物品for (int i = 0; i < num; ++i) {// 内层循环从 weights重量 逐渐减少到当前物品重量for (int j = weights; j - costs[i] >= 0; --j) {// 考虑当前物品选择和不选择的情况，选择最大值dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);}}// 输出dp[weights]，即在给定 weights 背包容量可以携带的物品最大价值cout << dp[weights] << endl;return 0;
}

推荐使用一维dp数组的写法，比较直观简洁，而且空间复杂度还降了一个数量级！

分割等和子集

抽象成：物品重量是nums[i]，物品价值也是nums[i]，背包容量是sum/2

(先物品类型后背包容量) 一维滚动数组的dp 考虑倒序遍历

dp[i]中的i表示背包内总和

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;// 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200// 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了vector<int> dp(10001, 0);for (int i = 0; i < nums.size(); i++) {sum += nums[i];}// 也可以使用库函数一步求和// int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2 == 1) return false;int target = sum / 2;for(int i = 0; i < nums.size(); i++) {for(int j = target; j - nums[i] >= 0; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}// 集合中的元素正好可以凑成总和targetif (dp[target] == target) return true;return false;}
};

完全背包

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件 (一般先物品后背包，重复取==不用倒序遍历背包)

如果求组合数就是外层for循环遍历物品类型，内层for遍历背包容量。

如果求排列数就是外层for遍历背包容量，内层for循环遍历物品类型。

滚动数组（组合数）

(此时为正序遍历)

class solution{public:int Get_big_value(vector<int>& values, vector<int>& weights, int weight){vector<int> dp(weight+1, 0);dp[0] = 0;for(int i = 0; i < weights.size(); i++){ for(int j =weights[i]; weight - j >= 0; j++){dp[j] = max(dp[j], dp[j-weights[i]] + values[i]);}}return dp[weight];} };

组合总和IV

(先背包容量后物品类型) 排列数问题递推公式： dp[i] += dp[i - nums[j]]

数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1, 0);dp[0] = 1;for (int i = 0; target - i >= 0; i++) {     // 遍历背包容量for (int j = 0; j < nums.size(); j++) { // 遍历物品类型if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
};

零钱兑换

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

组合数问题 (先遍历物品类型后遍历背包容量)

递推公式的特性为取min，考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1, INT_MAX);dp[0] = 0;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; amount -j >= 0; j++ ){if(dp[j-coins[i]] != INT_MAX)dp[j] = min(dp[j], dp[j-coins[i]] + 1);}}return dp[amount] == INT_MAX ? -1 : dp[amount];}
};

完全平方数

先物品类型后背包容量组合数问题

抽象成：物品类型为 i^2 (但是不能超过n) 背包容量为n

dp[j]：和为j的完全平方数的最少数量为dp[j]

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

单词拆分

（先背包容量后物品类型） (先背包容量或先物品类型，都需要考虑重量差)

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {//使用hash_set可以利用find方法unordered_set<string> word_set(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; i - j > 0; j++){   // 物品 i-j 容量差string cur_word = s.substr(j, i-j);  if(word_set.find(cur_word) != word_set.end() && dp[j]) // dp[j] 确保不交叉匹配dp[i] = true;}}return dp[s.size()];}
};

(先物品类型后背包容量)

将单词的长度抽象成 物品重量

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 j = 0; j < wordDict.size(); j++) {                    for (int i = wordDict[j].size(); s.size() - i >= 0; i++) { // s.size() - i 容量差string word = s.substr(i - wordDict[j].size(), wordDict[j].size());// cout << word << endl;if ( word == wordDict[j] && dp[i - wordDict[j].size()]) {dp[i] = true;}// for (int k = 0; k <= s.size(); k++) cout << dp[k] << " "; // cout << endl;}}return dp[s.size()];}
};

打家劫舍

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

如果偷第i房间， dp[i] = dp[i - 2] + nums[i]，即考虑 i-2房

如果不偷第i房间， dp[i] = dp[i - 1]，即考虑i-1房

dp数组初始化

vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

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() +1);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];}
};

打家劫舍II

(首尾相连的房子！)

class Solution {private://左闭右闭int rob_logic(vector<int>& nums, int start, int end){if (end == start) return nums[start];vector<int> dp(nums.size() +1);dp[start] = nums[start];                        //起始坐标dp[start+1] = max(nums[start],nums[start+1]);   for(int i = start+2; i <= end; i++){dp[i] = max(dp[i-1], dp[i-2] + nums[i]);}return dp[end];}
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];return max(rob_logic(nums, 0, nums.size() -2), rob_logic(nums, 1, nums.size()-1));}
};

打家劫舍III

动态规划其实就是使用状态转移容器来记录状态的变化

一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组

下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱

树形DP (后序遍历)

递推公式： val1 = cur->val + left[0] + right[0]; val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

// 偷cur，那么就不能偷左右节点。
// 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
class Solution {private:vector<int> backtracking(TreeNode* root){if(root == nullptr) return {0, 0};vector<int> left = backtracking(root->left);vector<int> right = backtracking(root->right);int val1 = root->val + left[0] + right[0];   // 偷curint val2 = max(left[1], left[0]) + max(right[1], right[0]);  //两条路各自比较 不偷curreturn {val2, val1};}
public:int rob(TreeNode* root) {vector<int> dp = backtracking(root);return max(dp[0], dp[1]);}
};

买卖股票

可以使用贪心算法作为一种思路 (也可以使用选择排序思路的暴力搜索，但是会超时)

dp[i][0] 表示第i天持有股票所得最多现金

dp[i][1] 表示第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]);

在未来的某一个不同的日子卖出该股票 (非同一天买入售出)

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], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
};

买卖股票II

(可以在同一天买入售出) 一只股票可以买卖多次

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(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]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[len - 1][1];}
};

买卖股票III

最多可以完成两次交易 (状态转移需要考虑四种状态)

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

dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j] 买卖股票(冷冻期(卖出后第二天不能买入))

递推公式：

达到买入股票状态（状态一）即：dp[i][0] 买入

dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

达到保持卖出股票状态（状态二）即：dp[i][1] dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

达到今天就卖出股票状态（状态三），即：dp[i][2] 卖出 dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：dp[i][3] dp[i][3] = dp[i - 1][2];

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if (n == 0) return 0;vector<vector<int>> dp(n, vector<int>(4, 0));dp[0][0] -= prices[0]; // 持股票for (int i = 1; i < n; i++) {dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - 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[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));}
};

股票买卖(含手续费)

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2, 0));dp[0][0] -= prices[0]; // 持股票for (int i = 1; i < n; 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 max(dp[n - 1][0], dp[n - 1][1]);}
};

子序列问题

子序列问题是动态规划解决的经典问题 (考虑连续与不连续)

最长递增子序列

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

递推公式(状态转移方程) if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1); 非连续

模拟过程类似滑动窗口

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int len = nums.size();int res = 1;vector<int> dp(len+1, 1);for(int i = 1; i< len; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]) dp[i] = max(dp[i],dp[j] +1);// 结果可能出现在中间遍历过程 ； 取长的子序列}res = max(dp[i], res);}return res;}
};

最长连续递增序列

双指针同向交替移动（不定长滑动窗口） (求连续时，是一个更替的问题！！！！)

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int left = 0;int res = 0;for(int right = 0; right < nums.size(); right++){if(right > 0 && nums[right-1] >= nums[right]) // 当不递增了，更新边界left = right;res = max(res, right -left +1);}return res;}
};

dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]

递推公式： if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1; (连续)

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

最长重复子数组

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]

递推公式： if( A[i-1] == B[j-1] ) dp[i][j] = dp[i - 1][j - 1] + 1; (连续子序列)

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

使用滚动数组 (需要倒序遍历！！！！)

class Solution {
public:int findLength(vector<int>& A, vector<int>& B) {vector<int> dp(vector<int>(B.size() + 1, 0));int result = 0;for (int i = 1; i <= A.size(); i++) {for (int j = B.size(); j > 0; j--) {if (A[i - 1] == B[j - 1]) {dp[j] = dp[j - 1] + 1;} else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作if (dp[j] > result) result = dp[j];}}return result;}
};

最长公共子序列

dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素 dp[i][j] = dp[i - 1][j - 1] + 1;

如果不相等就向前考虑 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); (非连续)

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] == 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()];}
};

不相交的线

直线不能相交，这就是说明在A中找到一个与B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。 (非连续)

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

最大子序和

dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。

转态转移方程： dp[i] = max(dp[i - 1] + nums[i], nums[i]); (连续子序列)

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

编辑距离问题

判断子序列

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

递推公式：if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; (非连续)

if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，dp[i][j] = dp[i][j - 1];

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] + 1;else dp[i][j] = dp[i][j - 1];}}if (dp[s.size()][t.size()] == s.size()) return true;return false;}
};

不同的子序列

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]

当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; (非连续)

当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配 dp[i][j] = dp[i - 1][j];

求的是 s 中有多少个 t，而不是求t中有多少个s，所以只考虑 s中删除元素的情况，即不用s[i - 1]来匹配的情况

dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1

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

两个字符串的删除操作

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候，删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

同时删word1[i - 1]和word2[j - 1]，最少操作次数为dp[i - 1][j - 1] + 2

递推公式： dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。

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 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] + 1, dp[i][j - 1] + 1);}}}return dp[word1.size()][word2.size()];}
};

编辑距离！！！！

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

if (word1[i - 1] == word2[j - 1]) 即不用任何编辑，dp[i][j] = dp[i - 1][j - 1];

if (word1[i - 1] != word2[j - 1]) 情况1 dp[i][j] = dp[i - 1][j] + 1; 情况2 dp[i][j] = dp[i][j - 1] + 1;

情况3 (替换元素) dp[i][j] = dp[i - 1][j - 1] + 1;

dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

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

回文子串

(左右向中间收缩) (重叠子问题) (bool的dp典题,对于回文问题采用相向遍历)

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false

当s[i]与s[j]相等时：

情况一：下标i 与 j相同，同一个字符例如a，情况二：下标i 与 j相差为1，例如aa，

情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分

所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

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;}}}
}

可以把选择分支转换为逻辑分支(逻辑分支会短路的)

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(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] && (j - i <= 1 || dp[i + 1][j - 1])) {result++;dp[i][j] = true;}}}return result;}
};

最长回文子序列

回文子串是要连续的，回文子序列可不是连续的！ ( 对于回文问题采用相向遍历)

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]

如果s[i]与s[j]相同，即： dp[i][j] = dp[i + 1][j - 1] + 2;

如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(), vector<int>(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.将问题分解为若干个子问题

2.找出适合的贪心策略

3.求解每一个子问题的最优解

4.将局部最优解堆叠成全局最优解

(常识性推导加上举反例！！！！) (需要贪心的场景潜在标志是可能用到排序sort 反转reverse 以及出现了一些最多最小最少最大数量等 “最数量” 字眼)

分发饼干

局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int index = s.size() - 1; // 饼干数组的下标int result = 0;for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口if (index >= 0 && s[index] >= g[i]) { // 遍历饼干result++;index--;}}return result;}
};

(编程技巧：用了一个 index 来控制饼干数组的遍历，采用自减的方式)

摆动序列

(动态规划的思路)

设 dp 状态dp[i][0]，表示考虑前 i 个数，第 i 个数作为山峰的摆动子序列的最长长度
设 dp 状态dp[i][1]，表示考虑前 i 个数，第 i 个数作为山谷的摆动子序列的最长长度

递推公式：

dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，表示将 nums[i]接到前面某个山谷后面，作为山峰。
dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，表示将 nums[i]接到前面某个山峰后面，作为山谷。

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {vector<vector<int>> dp(1001, vector<int>(2, 0));dp[0][0] = dp[0][1] = 1;for(int i = 1; i < nums.size(); i++){dp[i][0] = dp[i][1] = 1;for(int j = 0; j < i; j++){if(nums[j] < nums[i])dp[i][0] = max(dp[j][1] +1, dp[i][0]);   //第i个为山谷;前一个为山峰}for(int j = 0; j < i; j++){if(nums[j] > nums[i])dp[i][1] = max(dp[i][1], dp[j][0] + 1);   //第i个为山峰； 前一个为山谷}}return max(dp[nums.size()-1][0], dp[nums.size()-1][1]);}
};

贪心的思路

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

全局最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

贪心，让峰值尽可能的保持峰值，然后删除单一坡度上的节点

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size() <= 1) return nums.size();int cur_gap = 0, pre_gap = 0, res = 0;for(int i = 1; i < nums.size(); i++){cur_gap = nums[i] - nums[i-1];if((cur_gap < 0 && pre_gap >= 0) || (cur_gap > 0 && pre_gap <= 0)){   //pre取到0，同步初始化结果res++;pre_gap = cur_gap;}}return res+1;  //第一个数也算一个峰或谷}
};

最大子序和

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) {count += nums[i];if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）result = count;}if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和}return result;}
};

买卖股票的最佳时机II

(利润拆分是关键点！)

局部最优：收集每天的正利润，全局最优：求得最大利润。

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

跳跃游戏

(这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！)

局部最优解：每次取最大跳跃步数（取最大覆盖范围），全局最优解：最后得到整体最大覆盖范围，看是否能到终点。

class Solution {
public:bool canJump(vector<int>& nums) {int cover = 0;if (nums.size() == 1) return true; // 只有一个元素，就是能达到for (int i = 0; i <= cover; i++) { // 注意这里是小于等于covercover = max(i + nums[i], cover);if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了}return false;}
};

跳跃游戏II

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。全局最优：一步尽可能多走，从而达到最少步数。

统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖

class Solution {
public:int jump(vector<int>& nums) {if (nums.size() == 1) return 0;int curDistance = 0;    // 当前覆盖最远距离下标int ans = 0;            // 记录走的最大步数int nextDistance = 0;   // 下一步覆盖最远距离下标for (int i = 0; i < nums.size(); i++) {nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标if (i == curDistance) {                         // 遇到当前覆盖最远距离下标ans++;                                  // 需要走下一步curDistance = nextDistance;             // 更新当前覆盖最远距离下标（相当于加油了）if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束}}return ans;}
};

K次取反后最大化的数组和

局部最优：让绝对值大的负数变为正数，当前数值达到最大，全局最优：整个数组和达到最大。

class Solution {
static bool cmp(int a, int b) {return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& A, int K) {sort(A.begin(), A.end(), cmp);      for (int i = 0; i < A.size(); i++) { if (A[i] < 0 && K > 0) {A[i] *= -1;K--;}}if (K % 2 == 1) A[A.size() - 1] *= -1; int result = 0;for (int a : A) result += a;       return result;}
};

加油站

( 直接模拟； for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历 )

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {for(int i = 0; i < cost.size(); i++){int source = gas[i] - cost[i];int index = (i+1) % cost.size();while(source > 0 && index != i){source += gas[index] - cost[index];index = (index+1) % cost.size();}if(source >= 0 && index == i) return i;   //从i开始，环绕一周后剩余油量>=0}return -1;}
};

局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int totalSum = 0;int start = 0;for (int i = 0; i < gas.size(); i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {   // 当前累加rest[i]和 curSum一旦小于0start = i + 1;  // 起始位置更新为i+1curSum = 0;     // curSum从0开始}}if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了return start;}
};

多维度权衡

分发糖果

局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果

两次贪心的策略

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candy_distur(ratings.size(), 1);for(int i = 1; i < ratings.size(); i++){if(ratings[i] > ratings[i-1])candy_distur[i] = candy_distur[i-1] + 1;}for(int i = ratings.size() - 2; i>= 0; i--){if(ratings[i] > ratings[i+1])candy_distur[i] = max(candy_distur[i], candy_distur[i+1] + 1);   //确保比右边大1个即可}int res = 0;for(int i = 0; i< candy_distur.size(); i++){res += candy_distur[i];}return res;}
};

根据身高重建队列

(同分发糖果的贪心类似，多角度贪心)

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

插入[7,0]：[[7,0]]
插入[7,1]：[[7,0],[7,1]]
插入[6,1]：[[7,0],[6,1],[7,1]]
插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

(使用链表容器)

class Solution {
public:// 身高从大到小排（身高相同k小的站前面）static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort (people.begin(), people.end(), cmp);list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多for (int i = 0; i < people.size(); i++) {int position = people[i][1]; // 插入到下标为position的位置std::list<vector<int>>::iterator it = que.begin();while (position--) { // 寻找在插入位置it++;}que.insert(it, people[i]);}return vector<vector<int>>(que.begin(), que.end());}
};

用最少数量的箭引爆气球

一直贪心最小右边界

局部最优：尽可能地让气球的最小右边界内包含尽可能多的左边界全局最优：重叠的气球越多使用的弓箭越少

class Solution {
private:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}
public:int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;sort(points.begin(), points.end(), cmp);int result = 1; // points 不为空至少需要一支箭for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着，注意这里不是>=result++; // 需要一支箭}else {  // 气球i和气球i-1挨着points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界}}return result;}
};

无重叠区间

一直贪心最小右边界

class Solution {static bool cmp(vector<int>& num1, vector<int>& num2){return num1[0] < num2[0];}
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int res = 0;sort(intervals.begin(), intervals.end(), cmp);for(int i = 1; i < intervals.size(); i++){if(intervals[i][0] < intervals[i-1][1]){res++;intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);}else{continue;}}return res;}
};

划分字母区间

(分割字符串普遍的思路是暴力回溯)

class Solution {
public:void backtracking(string& s, int start, vector<int>& partition){if(start == s.size())return;int end = start;for(int i = start; i< s.size(); i++){end = max(end, (int)s.find_last_of(s[i]));if(i == end){partition.push_back(end - start +1);backtracking(s, end+1, partition);break;}}}vector<int> partitionLabels(string s) {vector<int> partition;backtracking(s, 0, partition);return partition;}
};

贪心：在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了

统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

(在一次循环中用双指针来切割)

class Solution {
public:vector<int> partitionLabels(string s) {vector<int> hash(27, 0);for(int i = 0; i < s.size(); i++){hash[s[i] - 'a'] = i;}int right = 0;int left = 0;vector<int> res;for(int i = 0; i < s.size(); i++){right = max(right, hash[s[i] - 'a']);if(i == right){res.push_back(right - left + 1);left = right + 1;}}return res;}
};

合并区间

贪心的角度还是寻找重叠区间

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 排序的参数使用了lambda表达式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});// 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间// 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为按照左边界排序的result.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠 }}return result;}
};

单调递增的数字

(判断数字单调递增的一般思路)

// 判断一个数字的各位上是否是递增bool checkNum(int num) {int max = 10;while (num) {int t = num % 10;if (max >= t) max = t;else return false;num = num / 10;}return true;}

贪心的策略：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。

(用一个flag来标记从哪里开始赋值9，直接在判断赋值对于100这种情况会出容易出岔子)

class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum = to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行int flag = strNum.size();for (int i = strNum.size() - 1; i > 0; i--) {if (strNum[i - 1] > strNum[i] ) {flag = i;strNum[i - 1]--;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

监控二叉树

0：该节点无覆盖
1：本节点有摄像头
2：本节点有覆盖

从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，全局最优：全部摄像头数量所用最少！

(空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了)

(递归结束之后，还要判断根节点，如果没有覆盖，result++)

class Solution {
private:int result;int traversal(TreeNode* cur) {if (cur == NULL) return 2;int left = traversal(cur->left);    // 左int right = traversal(cur->right);  // 右if (left == 2 && right == 2) return 0;else if (left == 0 || right == 0) {result++;return 1;} else return 2;}
public:int minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) { // root 无覆盖result++;}return result;}
};