​
算法的知识储备
​​
动态规划算法(重中之重)

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

不同路径II

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

class Solution {
public:
int uniquePathsWithObstacles(vector<vector>& 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 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 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
#include
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，初始值为0
vector<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& 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& values, vector& 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& nums, int target) {
vector 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& coins, int amount) {
vector 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 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& wordDict) {
//使用hash_set可以利用find方法
unordered_set word_set(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; 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& wordDict) {
unordered_set wordSet(wordDict.begin(), wordDict.end());
vector 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 dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
class Solution {
public:
int rob(vector& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
vector 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& nums, int start, int end){
if (end == start) return nums[start];
vector 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& 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 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 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& prices) {
int len = prices.size();
if (len == 0) return 0;
vector<vector> dp(len, vector(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& prices) {
int len = prices.size();
vector<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]); // 注意这里是和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& prices) {
int len = prices.size();
vector<vector> dp(len, vector(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& prices) {
int n = prices.size();
if (n == 0) return 0;
vector<vector> dp(n, vector(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& prices, int fee) {
int n = prices.size();
vector<vector> dp(n, vector(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& 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& 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& 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& nums1, vector& 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& A, vector& B) {
vector dp(vector(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> 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()];
}
};
不相交的线

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

class Solution {
public:
int maxUncrossedLines(vector& A, vector& B) {
vector<vector> dp(A.size() + 1, vector(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& nums) {
if (nums.size() == 0) return 0;
vector 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> 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] = 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> dp(word1.size() + 1, vector(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> 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 - 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> 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] && (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> 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];
}
};
贪心算法(需要一定数学思维)
核心思想：利用局部最优解去归纳全局最优解

(贪心与动态规划都适合解决重复子问题，角度不同)

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

分发饼干

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

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

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

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

class Solution {
public:
int jump(vector& 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& 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& gas, vector& 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& gas, vector& 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一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 0; // curSum从0开始
}
}
if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
return start;
}
};
多维度权衡
分发糖果

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

两次贪心的策略

class Solution {
public:
int candy(vector& ratings) {
vector 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& a, const vector& b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector<vector> reconstructQueue(vector<vector>& people) {
sort (people.begin(), people.end(), cmp);
list<vector> que; // list底层是链表实现，插入效率比vector高的多
for (int i = 0; i < people.size(); i++) {
int position = people[i][1]; // 插入到下标为position的位置
std::list<vector>::iterator it = que.begin();
while (position–) { // 寻找在插入位置
it++;
}
que.insert(it, people[i]);
}
return vector<vector>(que.begin(), que.end());
}
};

用最少数量的箭引爆气球

一直贪心最小右边界

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

class Solution {
private:
static bool cmp(const vector& a, const vector& b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector<vector>& 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& num1, vector& num2){
return num1[0] < num2[0];
}
public:
int eraseOverlapIntervals(vector<vector>& 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& 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 partitionLabels(string s) {
vector 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> merge(vector<vector>& intervals) {
vector<vector> result;
if (intervals.size() == 0) return result;
// 排序的参数使用了lambda表达式
sort(intervals.begin(), intervals.end(), [](const vector& a, const vector& 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;
}
};

​