算法的知识储备
动态规划算法(重中之重)
如果某⼀问题有很多重叠⼦问题，使⽤动态规划是最有效的
动规是由前⼀个状态推导出来的，⽽贪⼼是局部直接选最优的
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();
//如果在起点或终点出现了障碍，直接返回0
if (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，初始值为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<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]);
}
}
// 集合中的元素正好可以凑成总和target
if (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]; // 偷cur
int val2 = max(left[1], left[0]) + max(right[1], right[0]); //两条路各自比较 不偷cur
return {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++) { // 注意这里是小于等于cover
cover = 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一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 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;
}
};