本文记录作者刷题过程中与动态规划相关的题目。
一、爬楼梯类型
1、斐波那契数列
剑指 Offer 10- I. 斐波那契数列（简单难度）
509. 斐波那契数（简单难度）
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
输入：n = 2
输出：1
点评
写法1：
class Solution {
public:
/* 本题是动态规划的经典题目，和509的区别在于答案需要% 1000000007，这是测试数据n最大可取100，防止溢出
F(n)需要由F(n-1)和F(n-2)确定，已知第0和1个，求解第n个
动态规划的步骤：
定义
状态定义：F[n] 表示的含义为斐波那契数列中第 n 个数字
转移方程：F(n)=F(n-1)+F(n−2)，
求 n元素时，只需要知道第 n-1 和 n-2个元素即可，故而运算过程中不需要保存全部的dp数组
初始状态： F[0] = 0, F[1] = 1
*/
int fib(int n) {
if(n<=1) return n;
// 动态规划数组
vector<int> dp(n+1,0); //dp[i]表示第i个数的斐波那契数值
// 初始状态
dp[0]=0;// 第n-2个数
dp[1]=1;// 第n-1个数
// 遍历[2,n+1)计算第n个数的值
for(int i=2;i<=n;i++){
int temp = dp[i-1]+dp[i-2];//第n个数=第n-2个数+第n-1个数
temp=temp% 1000000007;//取模，防止数字溢出
dp[i]=temp;
}
return dp[n];
}
};
写法2：
class Solution {
public:
/* 本题是动态规划的经典题目，和509的区别在于答案需要% 1000000007，这是测试数据n最大可取100，防止溢出
F(n)需要由F(n-1)和F(n-2)确定，已知第0和1个，求解第n个
动态规划的步骤：
状态定义：F[n] 表示的含义为斐波那契数列中第 n 个数字
转移方程：F(n)=F(n-1)+F(n−2)，求 n元素时，只需要知道第 n-1 和 n-2个元素即可，故而运算过程中不需要保存全部的dp数组
初始状态： F[0] = 0, F[1] = 1
*/
int fib(int n) {
if(n<=1) return n;
// 动态规划数组
vector<int> dp(2); //dp[i]表示第i个数的斐波那契数值
// 初始状态
dp[0]=0;// 第n-2个数
dp[1]=1;// 第n-1个数
// 遍历[2,n+1)计算第n个数的值
for(int i=2;i<n+1;i++){
int temp = dp[0]+dp[1];//第n个数=第n-2个数+第n-1个数
temp=temp% 1000000007;//取模，防止数字移除
dp[0] = dp[1];//更新第n-2个数
dp[1] = temp;// 更新第n-1个数
}
return dp[1];
}
};
2、爬楼梯问题
剑指 Offer 10- II. 青蛙跳台阶问题（简单难度）
70. 爬楼梯（简单难度）
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
点评
class Solution {
public:
/* 本题是动态规划的经典题目，和70的区别在于答案需要% 1000000007，这是测试数据n最大可取100，防止溢出
本题和斐波那契数列数列几乎一样，唯一的区别在于初始状态不一样。
第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法
动态规划的步骤：
状态定义：F[n] 表示的含义为上一个n级台阶的跳法数目
转移方程：F(n)=F(n-1)+F(n−2)，求 n+1 元素时，只需要知道第 n 和 n-1 个元素即可，故而运算过程中不需要保存全部的dp数组
初始状态： F[0] = 1, F[1] = 1
*/
int numWays(int n) {
if(n==0) return 1;
if(n==1) return 1;
vector<int> dp={0,0};//爬到第i层楼梯，有dp[i]种方法
dp[0] = 1;
dp[1] = 1;
// 第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法
for(int i=2;i<n+1;i++){
int temp=dp[0]+dp[1];
temp=temp%1000000007;// 防止溢出
dp[0] = dp[1];
dp[1] = temp;
}
return dp[1];
}
};
746. 使用最小花费爬楼梯（简单难度）
剑指 Offer II 088. 爬楼梯的最少成本（简单难度）
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。
点评
整理后的代码如下：
int minCostClimbingStairs(vector<int>& cost) {
/*输入一个整型数组，输出一个数组
这道题要注意在楼梯上停留时需要支付体力值。例如[10,15,20]
爬完楼梯指的是人走到20的后一个，而不是走到20就算爬完，在这个案例中其至少需要站在i=1的台阶上，所以必然花费15。假设这个cost共有N个台阶，则人需要爬到第i=N个台阶（假设cost[N]=0）才算结束，则其只能是从第N-1个台阶或者第N-2个台阶上爬上来的，并且需要支付cost[N]，若每个dp[i]表示达到第i个台阶花费的最小体力则dp[N]=min(dp[N-1]，dp[N-2])+cost[N]。
思路：第i个台阶的最低体力=min(第i-1个台阶的最低体力，第i-2个台阶的最低体力)+cost[i],
爬到第 cost.size()个台阶才算爬完，设cost[cost.size()]=0
*/
int N = cost.size();
vector<int> dp(N+1);// 每个dp[i]表示达到第i个台阶花费的最小体力
dp[0]=cost[0];// 就一个台阶，只需要支付其体力就行
dp[1]=cost[1];// 两个台阶，但是cost[1]必须支付，所以直接从1出发
for(int i=2;i<=N;i++){
if(i!=N){
dp[i] = min(dp[i-1], dp[i-2])+cost[i];
}else{
dp[i] = min(dp[i-1], dp[i-2]);
}
}
return dp[N];//最后一步不需要花费
}
则另一个版本的代码如下：
int minCostClimbingStairs(vector<int>& cost) {
/*输入一个整型数组，输出一个数组
思路：第i个楼梯的最低体力=min(第i-1个楼梯的最低体力，第i-2个楼梯的最低体力)+cost[i]
*/
vector<int> dp={0,0};// 每个dp[i]表示达到第i个台阶花费的最小体力
dp[0]=cost[0];// 就一个台阶，只需要支付其体力就行
dp[1]=cost[1];// 两个台阶，但是cost[1]必须支付，所以直接从1出发
for(int i=2;i<cost.size();i++){
int temp = min(dp[0], dp[1])+cost[i];
dp[0] = dp[1];
dp[1] = temp;
}
return min(dp[0],dp[1]);//最后一步不需要花费
}
剑指 Offer 46. 把数字翻译成字符串（中等难度）
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
点评
class Solution {
public:
/* 解析：这道题定义0-25的数都可以翻译成对应的英文字母，给定一个多位数字，问有多少种方案
存在多种翻译方案的原因在于，每次翻译可以只翻译1个数位，也可以一次性翻译2个数位，例如：
16可以看做1和6分别进行翻译，也可以看做16一次性翻译
这道题可以看做是抽象的爬楼梯问题：给定一个n位数，就是给了n个台阶
每此只能翻译一个数或两个数就是，n个台阶里每此只能上一级或两级
唯一的区别是爬两级需要做一个是否小于26的判断。
【状态定义】：dp[i] 表示的含义为翻译前i个数字的方案数目
【转移方程】：翻译前i位数只能是
（1）第i位数字 无法和前面的数组合，比如 1245, 5 只能单独翻译，那么方法数和 124 是一样的
dp[i]=dp[i-1]，[i-2,i-1]组成的数<10||>25
（2）第i位数字 可以和前面的数组合，比如 1215, 5 可以选择 组合 和 不组合，最终结果为两种情况相加
a. 选择组合，15看成是整体，那么 dp[i] = dp[i - 2]
b. 不选择组合，5单独翻译，那么 dp[i] = dp[i - 1]
最终结果：
dp[i]=dp[i-1]+dp[i−2]，10<=[i-2,i-1]组成的数<=25
*/
int translateNum(int num) {
string numStr=to_string(num);
vector<int> dp={0,0};
dp[0]=1;
dp[1]=1;
// 循环[2,len]，因为dp[i]是定义前i位数字，最后求前len位数字
for(int i=2;i<=numStr.length();i++){
int temp=0;
int digit=(numStr[i-2]-'0')*10+numStr[i-1]-'0';
if(digit>=10&&digit<=25) temp=dp[0]+dp[1];
else temp=dp[1];
dp[0] = dp[1];
dp[1] = temp;
}
return dp[1];
}
};
3、网格路径（二维爬楼梯）
62. 不同路径(中等难度)
HJ91 走方格的方案数
int uniquePaths(int m, int n) {
/*输入两个整数，输出一个整数
思路：二维版本的爬楼梯，dp[i][j]=dp[i][j-1]+dp[i-1][j]
*/
vector<vector<int>> dp(m, vector<int>(n, 0));//dp[i][j]表示[0,0]到[i,j]需要多少条路径
//初始化数组
for(int i=0;i<m;i++) dp[i][0]=1;//第一行的每个位置都只有一条路径
for(int j=0;j<n;j++) dp[0][j]=1;//第一列的每个位置都只有一条路径
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
return dp[m-1][n-1];
}
剑指 Offer 47. 礼物的最大价值（中等难度）
class Solution {
public:
/*
【状态定义】dp[i][j]表示(0,0)到(i,j)的最大价值，求dp[m-1][n-1]
【状态转换】dp[i][j]=max(dp[i-1][j],dp[i][j-1])+gird[i][j]
【初始状态】
dp[0][0]=grid[0][0]
dp[i][0]=dp[i-1][0]+grid[i][0]
dp[0][j]=dp[0][j-1]+grid[0][j]
*/
int maxValue(vector<vector<int>>& grid) {
int m=grid.size();
int n=grid[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
dp[0][0]=grid[0][0];
for(int i=1;i<=m-1;++i){
dp[i][0]=dp[i-1][0]+grid[i][0];
}
for(int j=1;j<=n-1;++j){
dp[0][j]=dp[0][j-1]+grid[0][j];
}
for(int i=1;i<=m-1;++i){
for(int j=1;j<=n-1;++j){
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
};
63. 不同路径 II（中等难度）
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
/*输入一个二维数组，输出一个整数*/
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
vector<vector<int>> dp(m,vector<int> (n,0));
// 初始化数组
for(int i=0;i<m;i++){
if(obstacleGrid[i][0]!=1){
dp[i][0]=1;
}
else{
break;
}
}
for(int j=0;j<n;j++){
if(obstacleGrid[0][j]!=1){
dp[0][j]=1;
}
else{
break;
}
}
// 推导dp数组
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];
}
}
}
return dp[m-1][n-1];
}
64. 最小路径和（中等难度）
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小，返回最小的路径和即可。说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
点评
class Solution {
public:
/* 动态规划题目
【状态定义】dp[i][j]表示从(0,0)走到点(i-1,j-1)的最小路径和,最终求dp[m-1][n-1]
【状态转换】dp[i][j]只能由2个方向推导而来:dp[i-1][j]、dp[i][j-1]
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
【初始状态】显然i正序，j正序，需要知道dp[0][0]，显然为grid[0][0]
边界部分需要单独定义：
dp[i][0]=dp[i-1][0]+grid[i][0];
dp[0][j]=dp[0][j-1]+grid[0][j];
*/
int minPathSum(vector<vector<int>>& grid) {
int m=grid.size();
int n=grid[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
// 初始化
dp[0][0]=grid[0][0];
for(int i=1;i<m;++i) dp[i][0]=dp[i-1][0] +grid[i][0];
for(int j=1;j<n;++j) dp[0][j]=dp[0][j-1] +grid[0][j];
// 迭代
for(int i=1;i<m;++i){
for(int j=1;j<n;++j){
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
};
二、序列问题
1、最长递增子序列
300. 最长递增子序列（中等难度）
给定一个未经排序的整数数组 nums ，找到其中严格递增子序列的最长长度，子序列可以不连续。
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
class Solution {
public:
/* 动规经典问题
【状态定义】dp[j]表示以nums[j]结尾的最长上升子序列长度
【状态转移】对于任何的i属于[0,j-1],都有
if (nums[j] > nums[i]) dp[j] = max(dp[j], dp[i] + 1);
【初始状态】每个j对应的dp[j]都至少是1.
*/
int lengthOfLIS(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
vector<int> dp(nums.size(), 1);
int result = 0;
// 从数组中的第2个数开始遍历,当前遍历数为i
for (int j = 1; j < nums.size(); j++) {
// 遍历数组中的[i,j]
for (int i = 0; i < j; i++) {
if (nums[j] > nums[i]) dp[j] = max(dp[j], dp[i] + 1);
}
result=max(result,dp[j]);// 保存dp数组中的最长的长度
}
return result;
}
};
674. 最长连续递增序列（中等难度）
给定一个未经排序的整数数组 nums ，找到其中严格递增子序列的最长长度，子序列必须连续。
输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
点评
class Solution {
public:
/*动态规划问题
【状态定义】dp[i]表示以i结尾的数组的连续递增的子序列的长度
【状态转移】当nums[i]>nums[i-1]时,dp[i]=dp[i-1]+1
当nums[i]<=nums[i-1]时,dp[i]=1
【初始状态】dp[i]=1
*/
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size()+1,1);
int res=1;
dp[0]=1;
for(int i=1;i<nums.size();++i){
if(nums[i]>nums[i-1]) dp[i]=dp[i-1]+1;
else dp[i]=1;
res=max(res,dp[i]);
}
return res;
}
};
2、最长重复子序列
718. 最长重复子数组（中等难度）
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的连续子数组的长度 。
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
点评
class Solution {
public:
/* 连续子序列问题：动态规划
【状态定义】dp[i][j]表示以i-1结尾的nums1和以j-1结尾的nums2的重复子序列的长度
(i和j都从1遍历到结尾)
【状态转移】dp[i][j]由一个方向决定：dp[i-1][j-1]
nums1[i-1]==nums2[j-1]时，dp[i][j]=dp[i-1][j-1]+1
【初始状态】全部初始为0
时间复杂度和空间复杂度为O(nxm)
*/
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
int res=0;
for(int i=1;i<=nums1.size();++i){
for(int j=1;j<=nums2.size();++j){
if(nums1[i-1]==nums2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
res=max(res,dp[i][j]);
}
}
}
return res;
}
};
1143. 最长公共子序列（中等难度）
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度，如果不存在公共子序列 ，返回 0，公共子序列可以不连续 。
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
点评
class Solution {
public:
/* 最长重复子序列，子序列不连续
【状态定义】dp[i][j]表示长度为[0,i-1]的字符串text1和长度为[0,j-1]的字符串text2的公共子序列的最长长度
【状态转移】dp[i][j]由三个方向决定：dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]
text1[i-1]==text2[j-1]时，dp[i][j]=dp[i-1][j-1]+1
text1[i-1]!=text2[j-1]时，dp[i][j]=max(dp[i-1][j],dp[i][j-1])
【初始状态】全部初始化为0
*/
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.length()+1,vector<int>(text2.length()+1,0));
for(int i=1;i<=text1.length();++i){
for(int j=1;j<=text2.length();++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.length()][text2.length()];
}
};
1035. 不相交的线（中等难度）
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
当nums1[i] == nums2[j]时可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，同时要求该直线不能相交，即每个数字只能属于一条连线
以这种方法绘制线条，返回可以绘制的最大连线数。
nums1 = [1,4,2], nums2 = [1,2,4] 输出：2 解释：可以画出两条不交叉的线，如上图所示。 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
class Solution {
public:
/*本题本质上就是求nums1和nums2的最长重复子序列的长度，子序列可以不连续
【状态定义】dp[i][j]表示长度为[0,i-1]的字符串nums1和长度为[0,j-1]的字符串nums2的公共子序列的最长长度
【状态转移】dp[i][j]由三个方向决定：dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]
nums1[i-1]==nums2[j-1]时，dp[i][j]=dp[i-1][j-1]+1
nums1[i-1]!=nums2[j-1]时，dp[i][j]=max(dp[i-1][j],dp[i][j-1])
【初始状态】全部初始化为0
*/
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
for(int i=1;i<=nums1.size();++i){
for(int j=1;j<=nums2.size();++j){
if(nums1[i-1]==nums2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[nums1.size()][nums2.size()];
}
};
583. 两个字符串的删除操作（中等难度）
给定两个单词 word1 和 word2 ，每步 可以删除任意一个字符串中的一个字符。返回使得 word1 和 word2 相同所需的最小步数。
输入: word1 = “sea”, word2 = “eat” 输出: 2 解释: 第一步将 “sea” 变为 “ea” ，第二步将 “eat “变为 “ea”
点评
class Solution {
public:
/* 本题和1143题目接近：
求出两个字符串的最长重复子序列的长度，那么除了公共子序列剩余的字符都是要删除的
【状态定义】dp[i][j]表示长度为[0,i-1]的字符串text1和长度为[0,j-1]的字符串text2的公共子序列的最长长度
【状态转换】dp[i][j]由三个方向决定：dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]
word1[i-1]==word2[j-1]时，dp[i][j]=dp[i-1][j-1]+1
word1[i-1]!=word2[j-1]时，dp[i][j]=max(dp[i-1][j],dp[i][j-1])
【初始状态】全部初始化为0
*/
int minDistance(string word1, string word2) {
// 计算最长公共子序列的长度
vector<vector<int>> dp(word1.length()+1,vector<int>(word2.length()+1,0));
for(int i=1;i<=word1.length();++i){
for(int j=1;j<=word2.length();++j){
if(word1[i-1]==word2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
int max_len=dp[word1.length()][word2.length()];
return word1.length()-max_len+word2.length()-max_len;
}
};
3、最大子序列和
剑指 Offer 42. 连续子数组的最大和（简单难度）
53. 最大子数组和（简单难度）
给定一个整数数组 nums ，请返回其中连续子数组的最大和（子数组最少包含一个元素）。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
点评
class Solution {
public:
/* 最大和子序列问题，子序列必须连续,原始序列中可能存在负值
【状态定义】dp[i]表示以nums[i]结尾的连续子序列的最大和
【状态转移】dp[i]由1个方向决定：dp[i-1],其变化决定于nums[i-1]
共有三种可能：dp[i-1]（放弃累加nums[i]）、dp[i-1]+nums[i]（直接累加nums[i]）、nums[i]（从i开始重新累加）
因为是连续序列，所以排除dp[i-1]，如果放弃累加nums[i]，那么就得从nums[i]重新开始
dp[i]=max(dp[i-1]+nums[i],nums[i])
【初始状态】dp[0]=nums[0],因为取最大值，dp[i]的初始值应该尽可能小，至于有多小，可以取nums[0]或INT_MIN
*/
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size()+1,INT_MIN);
dp[0] = nums[0];
int res = dp[0];
for(int i=1;i<nums.size();++i){
dp[i]=max(nums[i],dp[i-1]+nums[i]);
res=max(res, dp[i]);
}
return res;
}
};
4、编辑距离
392. 判断子序列（简单难度）
给定字符串 s 和 t ，两个字符串都由小写字母组成，判断 s 是否为 t 的子序列，本题中的s可以是不连续的子序列。
输入：s = "abc", t = "ahbgdc"
输出：true
点评
class Solution {
public:
/* 子序列判断，子序列可以不连续
该题可以转换为求s和t的重复子序列的长度，最后判断这个长度是否等于s的长度即可
【状态定义】 dp[i][j]表示以s[i-1]结尾的字符串s和t[i-1]结尾的字符串t的重复子序列的长度
【状态转换】dp[i][j]可以由2个方向推导而来：dp[i-1][j-1]、dp[i][j - 1]
因为s是不连续的子序列，所以s不需要向前回退，t是原序列，可以跳过某些字符不能由dp[i-1][j]推导而来
s[i-1]==t[i-1]时，t中找到了s对应的字符，dp[i][j] = dp[i-1][j-1] + 1
s[i-1]!=t[i-1]时，t中没有找到了s对应的字符，dp[i][j] = dp[i][j - 1]
【初始状态】全部初始化为0
*/
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];
}
}
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
cout<<dp[i][j];
}
cout<<endl;
}
if (dp[s.size()][t.size()] == s.size()) return true;
return false;
}
};
115. 不同的子序列（困难难度）
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数，s的子序列可以是不连续的。
输入：s = “rabbbit”, t = “rabbit” 输出：3 解释： 如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。 rabbbit rabbbit rabbbit
点评
class Solution {
public:
/* s的不连续子序列中，可以得到t的个数
【状态定义】dp[i][j]表示以i-1为结尾的s子序列中随便删除元素，出现以j-1为结尾的t的个数为dp[i][j]。
【状态转换】假设dp[i][j] 就是s[i] 和t[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] = dp[i-1][j]
现在解释
(1)s[i] == t[j] 时，以s="rara" t = "ra" 为例，当i = 3, j = 1时，s[i] == t[j]。
此时分为2种情况，s串用最后一位的a + 不用最后一位的a。
如果用s串最后一位的a,那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]
如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j]
所以 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
(2)s[i] != t[j] 比如 s = "rarb" t = "ra" 还是当i = 3, j = 1时，s[i] != t[j]
此时显然最后的b想用也用不上啊。所以只能指望前面的"rar"里面是否有能匹配"ra"的
所以此时dp[i][j] = dp[i-1][j]
【初始状态】从递归公式中可知dp[i][0] 和dp[0][j]是必须初始化的
dp[i][0]表示以i-1为结尾的s可以随便删除元素，出现空字符串的情况个数，其结果一定是1，即删除所有元素
dp[0][j]表示以-1为结尾的s可以随便删除元素，出现以j-1为结尾t的情况个数，其结果一定是0
dp[0][0]表示以-1为结尾的s可以随便删除元素，出现空字符串的情况个数，其结果是1
*/
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()];
}
};
72. 编辑距离（困难难度）
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符 删除一个字符 替换一个字符
示例 1：
输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)
点评
class Solution {
public:
/*
【状态定义】dp[i][j]表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2的最近编辑距离。
【状态转移】dp[i][j]是由dp[i-1][j-1]、dp[i - 1][j]、dp[i][j - 1]三个方向推导而来
具体取决于s1[i-1]和s2[i-1]的关系：
s1[i-1]==s2[i-1]时，在s1[i-2]和s2[i-2]后面分别添加一个相同的字符，不需要操作，所以dp[i][j]=dp[i-1][j-1]
s1[i-1]!=s2[i-1]时，增删换三选一,取最小值
（1）尝试删除s1的一个字符：dp[i][j]=dp[i-1][j]+1:以下标i-2为结尾的s1与j-1为结尾的s2的最近编辑距离 再加上一个操作
（2）尝试删除s2的一个字符：dp[i][j]=dp[i][j-1]+1：以下标i-2为结尾的s2与j-1为结尾的s1的最近编辑距离 再加上一个操作
（3）尝试替换s1或者s2的一个字符：替换s1[i-1]或者s2[i-1]使其s1[i-1]==s2[i-1]
dp[i][j]=dp[i-1][j-1]+1：以下标i-2为结尾的s1与j-2为结尾的s2的最近编辑距离 再加上一个操作
取最小：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
【初始状态】
dp[i][0]表示以下标i-1为结尾的字符串word1和以下标0-1为结尾的字符串word2的最近编辑距离，其值是i
dp[0][j]表示以下标0-1为结尾的字符串word1和以下标j-1为结尾的字符串word2的最近编辑距离，其值是j
*/
int minDistance(string s1, string s2) {
vector<vector<int>> dp(s1.length()+1,vector<int>(s2.length()+1,0));
for(int i=0;i<=s1.length();++i) dp[i][0]=i;
for(int j=0;j<=s2.length();++j) dp[0][j]=j;
// 遍历两个字符串
for (int i = 1; i <= s1.size(); i++) {
for (int j = 1; j <= s2.size(); j++) {
// 如果相等，不操作
if (s1[i - 1] == s2[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[s1.size()][s2.size()];
}
};
5、回文子串
647. 回文子串（中等难度）
剑指 Offer II 020. 回文子字符串的个数（中等难度）
给定一个字符串 s ，请返回这个字符串中回文子串的数目，本题中的回文子串是正着读和倒过来读一样的字符串，且由原字符串s中的连续字符组成。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
点评
方法一：暴力破解法（时间复杂度为O(n^3)）
//方法一：暴力获取所有子串
int countSubstrings(string s) {
int res=0;
// 遍历所有的起始位置
for (int i = 0; i < s.length(); ++i) {
// 遍历所有的终止位置
for (int j = i; j < s.length(); ++j) {
//判断子串[i,j]是否是回文串
if (isHui(s.substr(i, j - i + 1)))res++;
}
}
return res;
}
bool isHui(string s){
int left=0;
int right=s.length()-1;
while(left<right){
if(s[left]!=s[right]){
return false;
}
else{
left++;
right--;
}
}
return true;
}
方法二：动态规划法（时间复杂度为O(n^2)，空间复杂度为O(n^2)）
class Solution {
public:
/* 回文子串，子串必须连续
【状态定义】dp[i][j]表示字符串s在[i,j]上是否是回文子串(左右都是闭区间)
【遍历顺序】对i是从大向小遍历，对j是从小向大遍历，则i相当于右指针，j相当于左指针
【状态转移】
子串长度为1，如a。这样的子串是回文子串
子串长度为2，如aa，这样的子串要判断前后端是否相同，即s[i] == s[j]，相同则是回文子串，不相同则不是
故有s[i]== s[j]&&j-i<=1为true时,dp[i][j] = true;
子串长度大于2。比如 ababa 这个字符记作串1，把两边的a去掉，也就是bab记作串2，
可以看出只要串2是一个回文串，那么左右各多了一个a的串1必定也是回文串。
所以当s[i]==s[j]时，自然要看dp[i+1][j-1]是不是一个回文串。
故有s[i]== s[j]&&dp[i+ 1][j-1]为true时,dp[i][j] = true;
【初始状态】全为true或者false都可以
*/
int countSubstrings1(string s) {
vector<vector<bool>>dp (s.size() + 1, vector<bool>(s.size() + 1, false));
int res = 0;
// 右指针i从大到小遍历
for (int i=s.size()-1; i >= 0; i--) {
// 左指针j从小到大遍历
for (int j=i; j<s.size(); j++) {
// 如果区间[i,j]的长度<=2，s[i]==s[j]
if(s[i]==s[j]&&j-i<=1){
res++;
dp[i][j] = true;
}
// 如果区间[i,j]的长度>2,s[i]==s[j]且dp[i+1][j-1]为真
else if(s[i]==s[j]&&dp[i+1][j-1]){
res++;
dp[i][j] = true;
}
}
}
return res;
}
};
方法三：双指针法（时间复杂度为O(n^2)，空间复杂度为O(1)）
/*
首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。
在遍历中心点的时候，要注意中心点有两种情况。
一个元素可以作为中心点，两个元素也可以作为中心点。
*/
int countSubstrings(string s) {
int res = 0;
// 遍历字符串s的每个字符，分别以其为中心进行扩散，
for (int i=0; i<s.size(); i++) {
res += extend(s, i, i, s.size()); // 以i为中心
res += extend(s, i, i + 1, s.size()); // 以i和i+1为中心
}
return res;
}
// 从字符串s的位置i和j分别向两端扩散，
int extend(string& s, int left, int right, int n) {
int res=0;
// 如果left和right扩散后仍然没有出界并且指的字符相等，
while(left>=0&&right<n&&s[left]==s[right]) {
left--;
right++;
res++;
}
return res;
}
5. 最长回文子串（中等难度）
给你一个字符串 s，找到 s 中最长的回文子串，如果有多个最长回文子串，随意输出一个即可。
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
点评
本题和647的代码高度相同。
class Solution {
public:
string longestPalindrome(string s) {
vector<vector<bool>>dp (s.size() + 1, vector<bool>(s.size() + 1, false));
string res;
int maxLen = 0;
// 右指针i从大到小遍历
for (int i=s.size()-1; i >= 0; i--) {
// 左指针j从小到大遍历
for (int j=i; j<s.size(); j++) {
// 如果区间[i,j]的长度<=2，s[i]==s[j]
if(s[i]==s[j]){
if(j-i<=1||dp[i+1][j-1]){
dp[i][j] = true;
int len=j-i+1;
if(len>maxLen) {
maxLen=len;
res=s.substr(i,len);
}
}
}
}
}
return res;
}
};
516. 最长回文子序列（中等难度）
给你一个字符串 s ，返回其中最长的回文子序列，注意，本题中的回文子序列可以在字符串s中不连续。
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
点评
class Solution {
public:
/* 动态规划法：回文子串，子串不连续
【状态定义】字符串s在[i,j]范围内最长的回文子序列的长度为dp[i][j]。
【状态转换】要求dp[i][j]就考虑s[i]与s[j]
i==j时,dp[i][j]=1
i!=j时,
s[i]==s[j]时,看中间回文长度可以直接拼接两边,dp[i][j]=dp[i+1][j-1]+2;
s[i]!=s[j]时,必定要舍弃其中一个字母,看舍弃哪个最后长度会更大
dp[i][j]=max(dp[i+1][j], dp[i][j-1]);
【初始状态】初始化dp[i][i]=1,其他为0，递归公式无法计算i和j相同的情况，需要手动初始化
【遍历顺序】先i后j,i倒序,j正序(dp[i][j]=dp[i+1][j-1]说明,i+1在i之前计算,j-1在j之前计算)
【返回形式】返回dp[0][len-1]
*/
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;
// 遍历dp
for (int i=s.size()-1; i>= 0; i--) {
for (int j=i; j<s.size(); j++) {
if(i==j){
dp[i][j]=1;
}
else 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、01背包问题
有N种具有体积和价值的物品，其中第i个物品的体积为weight[i]，价值为value[i]；每种物品都只有1个，放入一个容量为W的背包，问将哪些物品放入背包价值最大？
二维dp数组的写法
【状态定义】dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包的物品最大价值总和
【状态转移】按照是否放物品i来进行推导：
不放物品i：
dp[i][j]=dp[i-1][j]放物品i：
dp[i][j]=dp[i-1][j-weight[i]]+value[i]那么综合两种情况，取最大值：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
【初始状态】
背包容量为0时，最大价值一定都为0：
dp[i][0]=0只放入物品i=0时：
当背包容量j<weight[0]时，最大价值
dp[0][j]=0当背包容量j>=weight[0]时，最大价值
dp[0][j]=value[0]
相关代码：
// 背包容量为0时，最大价值一定都为0：dp[i][0]=0（可省略）
for (int j = 0 ; j < weight[0]; j++) dp[0][j] = 0;
// 只放入物品i=0时，当背包容量j>=weight[0]时，最大价值`dp[0][j]=value[0]`
for (int j = weight[0]; j <= bagWeight; j++) dp[0][j] = value[0];
相关模板：
vector<int> dp(weight.size(),vector<int>(bagWeight+1,0));//(物品种类数，背包最大容量数+1)
for(int j = weight[0]; j <= bagWeight; j++)dp[0][j] = value[0];
// 遍历物品的体积，即当前要添加物品的体积i
for(int i = 1; i < weight.size(); i++) { // 遍历物品
// 遍历背包容量，在当前背包容量为j时
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
// 如果新物品的体积比容量大，不可以添加，直接使用上一个值（剪枝）
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
// 如果新物品的体积比容量小，可以添加，计算新的价值
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
一维dp数组的写法
对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来
对于一维dp，dp[j]都是通过本层即dp[j]覆盖计算而来
【状态定义】dp[j] 表示容量为j的背包，可以放入的物品最大价值总和
【状态转移】按照是否放物品i来进行推导：
不放物品i：
dp[j]=dp[j]放物品i：
dp[j]=dp[j-weight[i]]+value[i]那么综合两种情况，取最大值：
dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
【初始状态】
在取最大价值时，dp数组全部初始化为0即可
相关模板：
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
// 一维数组的写法
vector<int> dp(weight.size(),vector<int>(bagWeight+1,0));//(物品种类数，背包最大容量数+1)
for(int j = weight[0]; j <= bagWeight; j++)dp[0][j] = value[0];
// 升序遍历物品的体积，即当前要添加物品的体积i
for(int i = 0; i < weight.size(); i++) { // 遍历物品
// 降序遍历背包容量，在当前背包容量为j时
for(int j = bagweight; j >=weight[i] ; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
在上述写法中，背包容量的遍历顺序是从大到小，且必须先遍历物品后遍历背包，这是因为为了保证物品i只被放入一次背包。
假设物品i=0的体积很小但是价值很大：weight[0] = 1，价值value[0] = 15，dp[]
如果正序遍历：
dp[1] = max(dp[1], dp[1 - weight[0]] + value[0])=max(0,0+15)=15;//在容量为j=1的背包放入了，价值为15
dp[2] = max(dp[2], dp[2 - weight[0]] + value[0])=max(0,15+15)=30;//在容量为j=2的背包放入了2次，价值为30
如果倒序遍历：
dp[2] = max(dp[2], dp[2 - weight[0]] + value[0])=max(0,0+15)=15;//在容量为j=2的背包放入了，价值为15
dp[1] = max(dp[1], dp[1 - weight[0]] + value[0])=max(0,0+15)=15;//在容量为j=1的背包放入了，价值为15
剑指 Offer II 101. 分割等和子集（简单难度）
416. 分割等和子集（中等难度）
给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
点评
nums的数组很大，用回溯法需要调优，很可能超时。
用动态规划法，将该问题看做一个01背包问题：
将[0,n-1]个体积和价值都为nums的物品放入容量为sum/2的背包,问背包中所有物品的最大价值（元素和）是否大于等于sum/2
所有的物品是[0,n-1]，所有的合法背包容量是[sum/2,nums[i-1]]
【问题类型】01背包，求能否恰好装满大小为sum/2的背包（先升序遍历物品后降序遍历背包）
【背包分析】
物品是可以用的整数，其weight是整数的数值[1,5,11,5] ,value是整数的数值[1,5,11,5]
背包是最终的目标和，其bagSize=sum/2
【状态转换方程】
dp[j]=max(dp[j]+dp[j-nums[i]]+nums[i])
【初始状态】
` dp[j]=0`
/*01背包问题：本题可以理解为是否存在可以将一些重量和价值相等的物品放入容量为sum/2的背包中
【状态定义】dp[j]表示容量为j的背包，可以放入的物品的最大总和
【状态转移】假设放入重量为nums[i]，价值为nums[i]的物品，dp[j]放入nums[i]前的背包容量为dp[j-nums[i]]
那么其价值为dp[j-nums[i]]+nums[i]，不放入该物品价值为dp[j]，放入该物品价值为dp[j-nums[i]]+nums[i]
当前价值为dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
【初始状态】dp[0]=0
*/
bool canPartition(vector<int>& nums) {
int n=nums.size();
int bagSize=0;
for(int n:nums) bagSize+=n;
if(bagSize%2!=0) return false;
bagSize=bagSize/2;
// 初始化二维数组
vector<int> dp(bagSize+1,0);// dp[i][j]表示将0-i的物品装入容量为j的背包中的最大价值
// 遍历所有的物品，物品是[0,n-1]
for(int i=0;i<n;i++){
// 遍历所有的背包,背包是[bagSize,nums[i]]
for(int j=bagSize;j>=nums[i];j--){
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
return dp[bagSize]>=bagSize;// 问从0~n-1个物品中取，放入容量为bagSize，问其最大元素和是否等于bagSize
}
方法二：
/*将[0,n-1]个体积和价值都为nums的物品放入容量为sum/2的背包,问背包中所有物品的最大价值（元素和）是否大于等于sum/2
所有的物品是[0,n-1]，所有的合法背包容量是[sum/2,nums[i-1]]*/
bool canPartition(vector<int>& nums) {
int n=nums.size();
int bagSize=0;
for(int n:nums) bagSize+=n;
if(bagSize%2!=0) return false;
bagSize=bagSize/2;
// 初始化二维数组
vector<vector<int>> dp(n,vector<int>(bagSize+1,0));// dp[i][j]表示将0-i的物品装入容量为j的背包中的最大价值
for(int j=nums[0];j<=bagSize;j++ ) dp[0][j]=nums[0];// 只可以放一个物品0的背包价值
// 遍历所有的物品
for(int i=1;i<n;i++){
// 遍历所有的背包
for(int j=0;j<=bagSize;j++){
if(j<nums[i]) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
}
}
return dp[n-1][bagSize]>=bagSize;
}
1049. 最后一块石头的重量 II（中等难度）
有一堆用整数数组 stones 表示的石头，其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头最小的可能重量 。如果没有石头剩下，就返回 0。
点评
该题和1046. 最后一块石头的重量的区别是：该题要求任意挑选两块石头，返回剩下石头的最小重量；1046是每次挑选最重的两块石头，返回剩余石头的重量。显然该题已经不能使用优先级队列或者堆来解答。
一个官方证明的结论：任意选i块石头，使得他们的重量趋近于总重量的一半，这样和另一半抵消的差值就是最小的
【问题类型】01背包，求装入为sum/2的背包中的最大物品价值（先升序遍历物品后降序遍历背包），最终结果是(sum-dp[target])-dp[target]
【背包分析】
物品是可以用的石头，其weight是石头的数值[1,5,11,5] ,value是石头的数值[1,5,11,5]
背包是最终的目标和，其bagSize=sum/2
【状态转换方程】
dp[j]=max(dp[j]+dp[j-stones[i]]+stones[i])
【初始状态】
` dp[j]=0`
class Solution {
public:
/*
一个官方证明的结论：任意选i块石头，使得他们的重量趋近于总重量的一半，这样和另一半抵消的差值就是最小的
所以该问题就可以转换为一个01背包问题：
在一堆重量和价值都为store[i]的物品中挑选，放入容量为sum/2的背包中，问背包最大可以容纳多少的物品
*/
int lastStoneWeightII(vector<int>& stones) {
int sum=0;
for(int stone:stones) sum+=stone;
int target=sum/2;
// 定义：dp[j]表示容量为j的背包最大可以容纳的石头，j的最大重量为30*100/2+1
vector<int> dp(target+1,0);
// 遍历物品
for(int i=0;i<stones.size();++i){
// 降序遍历背包
for(int j=target;j>=stones[i];--j){
dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
// 此时dp[target]就是所有石头中最趋近于总重量一半的重量，sum-dp[target]是另一半的重量
return (sum-dp[target])-dp[target];
}
};
474. 一和零（中等难度）
给定一个二进制字符串数组 strs 和两个整数 m 和 n 。返回 strs 的最大子集的长度，该子集中 最多有 m 个 0 和 n 个 1 。
点评
【问题类型】01背包，求恰好装满背包时所有物品的最大价值（先升序遍历物品后降序遍历背包）
【背包分析】
物品是可以用的二进制字符串，其weight1是二进制字符串的0的个数zeroNum ,其weight2是二进制字符串的1的个数oneNum ,value是二进制字符串的个数1
背包是最终限制的m和n，其bagSize1=m，bagSize2=n
【状态转换方程】
dp[i][j]=max(dp[i][j]+dp[i-zeroNum][j-oneNum]+1)
【初始状态】
dp[i][j] = 0
class Solution {
public:
/*01背包问题：在重量为0的个数，价值为1的个数的一堆物品中，放入容量为m的价值为n的背包中
该背包最多放入几个物品？
【状态定义】dp[i][j]表示容量为i的、价值为j的背包的最大物品数为dp[i][j]
【状态转换】dp[i][j]=dp[i-zeroNum][j - oneNum] + 1
*/
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
// 升序遍历物品
for (string str : strs) {
int oneNum = 0, zeroNum = 0;
// 统计0和1的数字
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
// 降序遍历背包
for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};
494. 目标和（中等难度）
给定一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个表达式 ，求共有几种表达式
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
点评
这题可以用回溯法，这里讲解动态规划法
原问题等同于： 找到nums一个正子集P和一个负子集N，使得总和等于target
假设nums = [1, 2, 3, 4, 5]，target = 3，一个可能的解决方案是+1-2+3-4+5 = 3
这里正子集P = [1, 3, 5]和负子集N = [2, 4]
那么sum(P) - sum(N) = target，sum(P) +sum(N) = sum(nums) ，可以得到：
sum(P) = （target + sum(nums)）/2，其中target + sum(nums)必须为偶数，否则不存在
该问题转换为：价值和重量都为nums[i]的物品中，放入容量为sum(P) 的背包中，问背包中的物品个数
【问题类型】01背包，求恰好装满背包时中所有物品的可能方案数（先升序遍历物品后降序遍历背包）
【背包分析】
物品是可以用的整数，其weight是整数的数值[1,1,1,1,1,1] ,value是整数的ID索引[0, 1]
背包是最终的目标和，其bagSize=(sum+target)/2
【状态转换方程】
dp[j]=dp[j]+dp[j-nums[i]]
【初始状态】
j=0时，dp[0] = 1
j>0时 dp[j]=0
/*01背包问题：用价值与体积均为nums[i]的物品,恰好凑满容量为(target+sum)/2的背包方案数：装几件物品
【状态定义】dp[j]为恰好能凑满容量为j的背包方案数
【状态转移】背包容量能或者不能装下nums[i]：
2.1 当不能装下nums[i]时,方案数直接继承之前的dp[j]
2.2 当能装下nums[i]时,总的方案数为不考虑nums[i]的方案数+有nums[i]参与新增的方案数
dp[j] += dp[j - nums[i]],dp[j - nums[i]]种方案与nums[i]共同凑成pos,即1*dp[j - nums[i]]
【状态初始】装满容量为0的背包，有1种方法，就是装0件物品。
*/
int findTargetSumWays(vector<int>& nums, int target) {
int sum=0;
for(int n:nums) sum+=n;
if (abs(target) > sum) return 0; // 此时没有方案
if((target+sum)%2!=0) return 0; // 此时没有方案
int bagSize=(target+sum)/2;
vector<int> dp(bagSize+1,0);
dp[0]=1;
// 升序遍历物品
for(int i=0;i<nums.size();++i){
// 降序遍历背包
for(int j=bagSize;j>=nums[i];--j){
dp[j]+=dp[j-nums[i]];
}
}
return dp[bagSize];
}
2、完全背包问题
一维数组的写法
有N种具有体积和价值的物品，其中第i个物品的体积为weight[i]，价值为value[i]；每种物品都有无数个，放入一个容量为W的背包，问将哪些物品放入背包价值最大？相关模板：
// 先遍历背包，再遍历物品
void test_CompletePack() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
// 初始化dp数组
vector<int> dp(bagWeight + 1, 0);
// 升序遍历物品体积
for(int i = 0; i < weight.size(); i++) { // 遍历物品
// 升序遍历背包容量
for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
在完全背包中，遍历物品体积和遍历背包容量的先后顺序无所谓
排列数和组合数
vector<int> dp(target + 1, 0);
dp[0] = 1;
// 先遍历背包+后遍历物品，得到排列数
for (int j = 0; j <= target; j++) {
for (int num:nums) {
if (j - num >= 0 && dp[j] < INT_MAX - dp[j - num]) {
dp[j] += dp[j - num];
}
}
}
// 先遍历物品+后遍历背包，得到组合数
for(int num:nums){
for(int j=num;j<=target;j++){
dp[j]+=dp[j-num];
}
}
return dp[target];
322. 零钱兑换（中等难度）
给你一个整数数组 coins ，表示不同面额的硬币，可以认为每种硬币的数量是无限的；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
点评
【问题类型】完全背包求其中物品的最少价值（组合数，先物品后背包）
【背包分析】
物品是硬币，其weight是硬币的面值[1, 2, 5] ,value是硬币的个数[1, 1, 1]
背包是兑换的目标金额，其bagSize=amount
问题相当于求装满背包的最少价值，如果背包没有装满，返回-1，如果装满了返回其最少价值。
【状态转换方程】
dp[j]=min(dp[j],dp[j-coin[i]]+1)
【初始状态】
j=0时，dp[0] = 0
j>0时 dp[j]=INT_MAX-1
class Solution {
public:
/* 假设有面值为 1, 2, 5的硬币，原问题是求金额i时的最少硬币数，
就是求 i-1，i-2，i-5 的三个子问题中的最少硬币数，
然后加一（再选一枚面值为 1, 2, 5 的硬币）
因为硬币数量没有限制，所以子问题之间没有相互制约，相互独立，即符合最优子问题。
dp(i)=min(dp(i-1)+1,dp(i-2)+1,dp(i-5)+1)
【定义dp】凑足总额为i的所需钱币最少个数为dp[i]
【状态转移】凑足总额为i的所需钱币最少个数为dp[i]=min(dp[i],1+dp[i-coin[j]]),j负责遍历coin数组
【初始条件】dp[0]=0，dp[-1]=-1，
*/
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX-1);//数组大小为amount+1，初始值为一个比该题目中答案都大的值
dp[0] = 0;
// 遍历所有的硬币的选择（物品）
for (int coin:coins) { // 遍历物品
// 遍历所有的amount（背包）
for (int i = 0; i < amount+1; i++) {
// 如果子问题有解
if (i- coin>=0) {
dp[i] = min(dp[i],1+dp[i -coin]);
}
}
}
// 如果硬币没法凑出金额，那么dp[amount]为初始值
if (dp[amount] == INT_MAX-1) return -1;
return dp[amount];
}
};
518. 零钱兑换 II（中等难度）
给你一个整数数组 coins ，表示不同面额的硬币，可以认为每种硬币的数量是无限的；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的硬币组合的个数 。如果没有任何一种硬币组合能组成总金额，返回 0。
输入：coins = [1, 2, 5], amount = 5
输出：4
解释：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
点评
【问题类型】完全背包求恰好装满背包时所有物品的可能方案（组合数，先物品后背包）
【背包分析】
物品是硬币，其weight是硬币的面值[1, 2, 5] ,value是硬币的ID索引[0, 1, 2]
背包是兑换的目标金额，其bagSize=amount
【状态转换方程】
dp[j]=dp[j]+dp[j-coin[i]]
【初始状态】
j=0时，dp[0] = 1
j>0时 dp[j]=0
class Solution {
public:
/* 完全背包问题:向容量为amount的背包放入不同种类的体积和价值都为coins[i]的物品
【状态定义】dp[j]表示可以凑出金额j的组合个数（不强调元素之间的顺序）
【状态转移】在容量为j的背包里放第i个硬币coins[i]
放第i个硬币的组合数：dp[j]=dp[j-coins[i]];// 容量为j的组合数和容量为j-coins[i]的组合数一样
不放第i个硬币的组合数：dp[j]=dp[j]//使用(0,i-1)的结果
综合来看共有dp[j]=dp[j]+dp[j-coins[i]];
【初始状态】dp[0]=1
【遍历顺序】先物品后背包
*/
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1,0);
dp[0]=1;
// 升序遍历所有物品
for(int coin:coins){
// 升序遍历所有背包容量
for(int j=coin;j<=amount;j++){
dp[j]+=dp[j-coin];
}
}
return dp[amount];
}
};
70. 爬楼梯（简单难度）
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
点评
【问题类型】完全背包，求恰好装满背包时中所有物品的可能方案（排列数，先背包后物品）
【背包分析】
物品是可以爬的台阶数{1,2}，其weight是可以爬的台阶数的数值[1, 2] ,value是可以爬的台阶数的ID索引[0, 1]
背包是要爬的n阶楼梯，其bagSize=n
【状态转换方程】
dp[j]=dp[j]+dp[j-weight[i]]
【初始状态】
j=0时，dp[0] = 1
j>0时 dp[j]=0
class Solution {
public:
/* 完全背包问题：容量为n的背包中放入体积为1或2的物品，问背包中放入物品的排列数
*/
int climbStairs(int n) {
vector<int> weights={1,2};
vector<int> dp(n+1,0);
dp[0]=1;
for(int j=0;j<=n;++j){
for(int weight:weights){
if(j-weight>=0){
dp[j]=dp[j]+dp[j-weight];
}
}
}
return dp[n];
}
};
377. 组合总和 Ⅳ（中等难度）
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。注意，数组nums中的每个数组可以使用多次，顺序不同的序列是做不同的组合。
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 点评
【问题类型】完全背包求恰好装满背包时所有物品的可能方案（排列数，先背包后物品）
【背包分析】
物品是不同的整数，其weight是整数的数值[1, 2, 3] ,value是整数的ID索引[0, 1, 2]
背包是寻找的目标和，其bagSize=target
【状态转换方程】
dp[j]=dp[j]+dp[j-nums[i]]
【初始状态】
j=0时，dp[0] = 1
j>0时 dp[j]=0
/* 完全背包问题：向容量为target的背包中放入体积和价值都为nums[i]的物品
问恰好放满背包的排列数量？
【状态定义】dp[j]表示容量为j的背包恰好放满的数量
【状态转移】dp[j]=dp[j]+dp[j-nums[i]]
【初始状态】dp[0] = 1
【遍历顺序】先背包后物品，注意dp[j] < INT_MAX - dp[j - num]
*/
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
// 升序遍历所有的背包容量
for (int j = 0; j <= target; j++) {
// 升序遍历所有的物品体积
for (int num:nums) {
if (j - num >= 0 && dp[j] < INT_MAX - dp[j - num]) {
dp[j] =dp[j]+ dp[j - num];
}
}
}
return dp[target];
}
279. 完全平方数（中等难度）
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数可以重复。
示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
点评
【问题类型】完全背包求恰好装满背包时中物品的最少价值（组合数，先物品后背包）
【背包分析】
物品是不同的完全平方数，其weight是完全平方数的数值[1, 4, 9] ,value是完全平方数的个数[1, 1, 1]
背包是寻找的目标和，其bagSize=target
问题相当于求装满背包的最少价值，如果背包没有装满，返回某个数（题目中不存在该情况），如果装满了返回其最少价值。
【状态转换方程】
dp[j]=min(dp[j]+dp[j-i*i]+1)
【初始状态】
j=0时，dp[0] = 0
j>0时 dp[j]=INT_MAX-1
class Solution {
public:
/*完全背包问题： 向一个容积为n的背包中放入体积为完全平方数的物品，问背包中恰好放满时的物品的最少数量
【状态定义】dp[j]表示容量为j的背包恰好放满的最少物品数量
【状态转移】对于第i个物品：
不放入：dp[j]=dp[j]
放入：dp[j]=dp[j-weight[i]]+1
综上：dp[j]=min(dp[j],1+dp[j-weight[i]])
【初始状态】dp[0]=0
*/
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX-1);// 取最小值，则初始值必须为最大值
dp[0]=0;
// 遍历物品
for(int i=1;i*i<=n;i++){
int weight=i*i;
// 遍历背包容量
for(int j=weight;j<=n;j++){
dp[j]=min(dp[j],1+dp[j-weight]);
}
}
if(dp[n]==INT_MAX-1) return -1;// 题目的测试数据中不存在该情况
else return dp[n];
}
};
139. 单词拆分（中等难度）
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
点评
【问题类型】完全背包求是否可以恰好装满背包（组合数，先物品后背包）
【背包分析】
物品是不同的字符单词（在搜索时特殊，从s中搜索区间，判断是否存在wordDict中），其weight是字符单词的值 ,value是是否匹配s中的某个区间
背包是匹配的目标字符串s，其bagSize=s.length()
【状态转换方程】
if (wordSet.count(word)&& dp[i]) dp[j] = true;
【初始状态】
j=0时，dp[0] = true
j>0时 dp[j]=false
class Solution {
public:
/* 完全背包问题：容量为s的背包中放入体积为wordDict的物品
【状态定义】dp[j]表示s的长度为i时，可以拆分字典中的单词为j的背包是否可以恰好放入物品
【状态转移】对于物品wordDict[i]
如果原来的dp[j] 是true，且 [i, j] 这个区间的子串出现在字典里，那么dp[j]一定是true。（i < j ）。
【初始状态】dp[0]=true
*/
bool wordBreak(string s, vector<string>& wordDict) {
// 将单词字典存入哈希集合
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
// 动态数组
int n=s.length();
vector<bool> dp(n + 1, false);
dp[0] = true;
// 遍历所有的物品
for (int i = 0; i < n; i ++){
// 遍历所有的字符串的长度
for (int j = i; j <= n; j++){ // 遍历物品
string word = s.substr(i, j - i); //substr(起始位置，截取的个数)
// 如果单词字典中存在该单词并且上一个区间也是true
if (wordSet.count(word)&& dp[i]) {
dp[j] = true;
}
}
}
return dp[n];
}
};
四、股票问题
剑指 Offer 63. 股票的最大利润（中等难度）
121. 买卖股票的最佳时机（简单难度）
2016. 增量元素之间的最大差值（简单难度）
class Solution {
public:
/*解析：
股票问题是动态规划的经典应用场景，本题是股票类中最简单的一个问题
买卖一次股票的最大利润意味着必须在股票价格最小值买入，最小值之后的股票价格最大值卖出。
本题只要求出最小值，和最小值之后的最大值就能通过。
但是我们重点放在动态规划的思路上：
【状态定义】：dp[i] 表示的含义为价格数组中0-i的子数组的最大利润,i<n
【转移方程】：假设
前n天的最大利润 = max(前n-1天的最大利润，第n天的价格 - 前n天的最低价格)
dp[i] = max(dp[i-1], min(prices[n], minCost))
【初始状态】： dp[0] = 0
*/
int maxProfit1(vector<int>& prices) {
int minCost = INT_MAX;
int res=0;
for(int price:prices){
minCost = min(minCost,price);
res=max(res,price-minCost);
}
return res;
}
class Solution {
public:
/* 该题只可以买卖一次股票，那么一定是在价格最低点买入，价格最高点卖出时利润最大
本质上是求一个整数数组内最大值和最小值的差
动态规划
【状态定义】prices中的每个数字都有3个操作：不操作、买入、卖出
但是这3个操作不是相互独立的，买入必须在不操作后，卖出必须在买入后
对应有2个状态，持有和不持有，所以dp可以看做是[n,2]维度
dp[i][0]表示第i天持有股票所得最多利润，dp[i][1]表示第i天不持有股票所得最多利润
注意，这里的持有不一定就是买入，可能是刚买入，也可能是继续持有的状态
【状态转换】
dp[i][0]=max(dp[i-1][0], -prices[i]);// 第i天继续持有，第i天新买入（前期卖出利润（0）-当前价格）
dp[i][1]=max(dp[i-1][1], prices[i]+dp[i-1][0]);// 第i天不继续持有，第i天新卖出（前期买入利润+当前价格）
【初始状态】
dp[0][0]表示第0天持有股票，此时持有股票一定就是买入股票了，dp[0][0]=-prices[0];
dp[0][1]表示第0天不持有股票，不持有股票那么利润就是0，所以dp[0][1] = 0;
【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出
*/
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2));
dp[0][0]=-prices[0];
dp[0][1] = 0;
for(int i=1;i<n;++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[n-1][1];
}
};
};
122. 买卖股票的最佳时机 II（中等难度）
给定一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。求你能获得的最大利润 。
输入：prices = [7,1,5,3,6,4] 输出：7 解释：
在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 获得利润 5 - 1 = 4 。 在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 获得利润 6 - 3 = 3 。 总利润为 4 + 3 = 7 。
点评
最大利润一定是在每次股票上涨前买入，下跌前卖出。
方法一：双指针法
/*该题可以多次买卖股票，那么一定是在价格上升前买入，价格下降前卖出利润最大
本质上是求一个整数数组内所有上升区间的累加和*/
int maxProfit(vector<int>& prices) {
int n = prices.size();
int res=0;// 结果
int begin=0;// 递增区间的起始位置
int end=0;// 递增区间的结束位置
// 遍历数组，查找所有递增区间，累加prices[end]-prices[begin]
for(int i=1;i<n;++i){
// 如果当前数是递增的
if(prices[i]>prices[i-1]){
end++;// 结束指针移动
// 如果当前位置是数组最后一个，添加最后一个递增区间
if(i==n-1){
res+=prices[end]-prices[begin];
}
}
// 如果当前数是非递增的
else{
// 添加之前的递增区间
res+=prices[end]-prices[begin];
// 重置递增区间
begin=i;
end=i;
}
}
return res;
}
方法二：动态规划法
class Solution {
public:
/* 该题可以多次买卖股票，那么一定是在价格上升前买入，价格下降前卖出利润最大
本质上是求一个整数数组内所有上升区间的累加和
动态规划：
【状态定义】prices中的每个数字都有3个操作：不操作、买入、卖出
但是这3个操作不是相互独立的，初次买入必须在不操作后，再次买入必须在卖出后，卖出必须在买入后
可以对应有2个状态，持有股票和不持有股票，所以dp可以看做是[n,2]维度
dp[i][0]表示第i天持有股票所得最多利润，dp[i][1]表示第i天不持有股票所得最多利润
注意，这里的持有不一定就是买入，可能是刚买入，也可能是继续持有的状态
【状态转换】
因为可以买卖多次，所以第i天可能手中可能有前期买卖的利润
如果只能买卖一次，第i天手中买入说明前期都没有利润
dp[i][0]=max(dp[i-1][0], dp[i-1][1]-prices[i]);// 第i天继续持有，第i天新买入，必须在第i-1天没有持有时操作（前期卖出利润-当前价格）
dp[i][1]=max(dp[i-1][1], dp[i-1][0]+prices[i]);// 第i天不继续持有，必须在第i-1天有持有时操作，第i天新卖出（前期买入利润+当前价格）
【初始状态】
dp[0][0]表示第0天持有股票，此时持有股票一定就是买入股票了，dp[0][0]=-prices[0];
dp[0][1]表示第0天不持有股票，不持有股票那么利润就是0，所以dp[0][1] = 0;
【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出
*/
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2));
dp[0][0]=-prices[0];
dp[0][1] = 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]);
}
return dp[n-1][1];
}
};
714. 买卖股票的最佳时机含手续费（中等难度）
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
点评
class Solution {
public:
/* 该题可以多次买卖股票，但是每笔交易都需要额外的手续费
动态规划：
【状态定义】prices中的每个数字都有3个操作：不操作、买入、卖出（同时支付手续费）
但是这3个操作不是相互独立的，买入必须在不操作后，卖出必须在买入后
可以对应有2个状态，持有股票和不持有股票，所以dp可以看做是[n,2]维度
dp[i][0]表示第i天持有股票所得最多利润，dp[i][1]表示第i天不持有股票所得最多利润
注意，这里的持有不一定就是买入，可能是刚买入，也可能是继续持有的状态
【状态转换】
因为可以买卖多次，所以第i天可能手中可能有前期买卖的利润
如果只能买卖一次，第i天手中买入说明前期都没有利润
dp[i][0]=max(dp[i-1][0], dp[i-1][1]-prices[i]);// 第i天继续持有，第i天新买入，必须在第i-1天没有持有时操作（前期卖出利润-当前价格）
dp[i][1]=max(dp[i-1][1], dp[i-1][0]+prices[i]-fee);// 第i天不继续持有，必须在第i-1天有持有时操作，第i天新卖出（前期买入利润+当前价格）
【初始状态】
dp[0][0]表示第0天持有股票，此时持有股票一定就是买入股票了，dp[0][0]=-prices[0];
dp[0][1]表示第0天不持有股票，不持有股票那么利润就是0，所以dp[0][1] = 0;
【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出
*/
int maxProfit(vector<int>& prices,int fee) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2));
dp[0][0]=-prices[0];
dp[0][1] = 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 dp[n-1][1];
}
};
123. 买卖股票的最佳时机 III（困难难度）
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
点评
class Solution {
public:
/* 该题可以最多2次买卖股票
本质上是求一个整数数组内所有上升区间中最大的两个上升区间的累加和
注意：这两个上升区间中允许存在小范围的下降，所以判断上升区间变得比较难
动态规划：
【状态定义】prices中的每个数字都有5个状态，
0（没有操作）1（第1次买入）2（第1次卖出）3（第2次买入）4（第2次卖出）
这5个操作不是相互独立的，0必须在0基础上操作，1必须在0之后操作，2必须在1之后操作，3必须在2之后操作，4必须在3之后操作
对应5种状态，设dp是[n,5]维度
dp[i][0]表示第i天没有操作的利润，该值恒为0
dp[i][1]表示第i天持有的股票利润，此时可能是第1次新买入，也可能没有操作（第i-1天就持有股票）
dp[i][2]表示第i天不持有的股票利润，此时可能是第1次新卖出，也可能没有操作（第i-1天就不持有股票）
dp[i][3]表示第i天持有的股票利润，此时可能是第2次新买入，也可能没有操作（第i-1天就持有股票）
dp[i][4]表示第i天不持有的股票利润，此时可能是第2次新卖出，也可能没有操作（第i-1天就不持有股票）
【状态转换】
因为可以买卖多次，所以第i天可能手中可能有前期买卖的利润
dp[i][0]=dp[i-1][0];//第i天什么也不操作，沿用上次
dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i]);// 第i天继续持有或第i天第1次新买入
dp[i][2]=max(dp[i-1][2], dp[i-1][1]+prices[i]);// 第i天不继续持有或第i天第1次新卖出
dp[i][3]=max(dp[i-1][3], dp[i-1][2]-prices[i]);// 第i天继续持有或第i天第2次新买入
dp[i][4]=max(dp[i-1][4], dp[i-1][3]+prices[i]);// 第i天不继续持有或第i天第2次新卖出
【初始状态】
dp[0][0]表示第0天没有操作，dp[0][0]=0
dp[0][1]表示第0天持有股票，此时持有股票一定就是第1次买入股票了，dp[0][1]=-prices[0];
dp[0][2]表示第0天不持有股票，此时持有股票一定就是第1次卖出股票了，因为不可以未买先卖，dp[0][2] = 0;
dp[0][3]表示第0天持有股票，此时持有股票一定就是第2次买入股票了，dp[0][3]=-prices[0];
dp[0][4]表示第0天不持有股票，此时持有股票一定就是第2次卖出股票了，因为不可以未买先卖，dp[0][4] = 0;
【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出*/
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(5,0));
dp[0][1]=-prices[0];
dp[0][3]=-prices[0];
for(int i=1;i<n;++i){
//dp[i][0]=dp[i-1][0];//第i天什么也不操作，可以不写，因为都是0
dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i]);// 第i天继续持有或第i天第1次新买入（前期卖出利润-当前价格）
dp[i][2]=max(dp[i-1][2], dp[i-1][1]+prices[i]);// 第i天不继续持有或第i天第1次新卖出（前期卖出利润+当前价格）
dp[i][3]=max(dp[i-1][3], dp[i-1][2]-prices[i]);// 第i天继续持有或第i天第2次新买入（前期买入利润-当前价格）
dp[i][4]=max(dp[i-1][4], dp[i-1][3]+prices[i]);// 第i天不继续持有或第i天第2次新卖出（前期买入利润+当前价格）
}
return dp[n-1][4];
}
};
188. 买卖股票的最佳时机 IV（困难难度）
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
点评
class Solution {
public:
/* 该题可以最多k次买卖股票
是123的扩展版，可根据123题的答案找出规律*/
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if(n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(2*k+1,0));
for (int j = 1; j < 2*k; j +=2) {
dp[0][j]=-prices[0];
}
for(int i=1;i<n;++i){
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i]);// 第i天继续持有或第i天第1次新买入（前期卖出利润-当前价格）
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i]);// 第i天不继续持有或第i天第1次新卖出（前期卖出利润+当前价格）
}
}
return dp[n-1][2*k];
}
};
309. 最佳买卖股票时机含冷冻期（中等难度）
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
点评
/* 该题可以多次买卖股票，但是每次卖出股票后都无法继续操作
动态规划：
【状态定义】prices中的每个数字都有3个操作：不操作、买入、卖出、冷冻期
这4个操作不是相互独立的，买入必须在不操作后，卖出必须在买入后，冷冻期必须在卖出后且只能为1天
可以对应有4个状态，dp可以看做是[n,4]维度：
0(今天持有股票：可能是今天新买入，也可能是之前就买入了股票然后没有操作)
1(今天不持有股票：昨天就不持有股票今天没有操作，之后不是冷冻期)
2(今天不持有股票：昨天持有股票今天卖出，之后是冷冻期)
3(今天为冷冻期，不可以买卖)
dp[i][0]表示第i天为状态0的利润
dp[i][1]表示第i天为状态1的利润
dp[i][2]表示第i天为状态2的利润
dp[i][3]表示第i天为状态3的利润
【状态转换】
状态转换：0、1、3—>0；1、3—>1；0—>2；2—>3
0持有股票状态的三种情况：
昨天就持有股票今天没有操作,在状态0上继续沿用：dp[i][0]=dp[i-1][0]
昨天是冷冻期今天新买入，在状态3上减去费用：dp[i][0]=dp[i-1][3]-prices[i]]
昨天不是冷冻期今天新买入，在状态1上减去费用：但前一天不是冷冻期,在状态1上减去费用：dp[i][0]=dp[i-1][1]-prices[i]
综上dp[i][0] = max(dp[i - 1][0], max(dp[i-1][3], dp[i-1][1])-prices[i]);
1今天不持有股票：昨天就不持有股票今天没有操作，之后不是冷冻期
昨天就是状态二或者昨天是冷冻期，即状态3
dp[i][1] = max(dp[i-1][1], dp[i-1][3]);
2今天不持有股票：昨天持有股票今天卖出，之后是冷冻期，在装填0的基础上操作：
dp[i][2] = dp[i-1][0] + prices[i];
3今天是冷冻期，不可以买卖，沿用状态2：
dp[i][3] = dp[i-1][2];
【初始状态】
dp[0][0]表示第0天持有股票，此时持有股票一定就是买入股票了，dp[0][0]=-prices[0];
dp[0][1]表示第0天不持有股票，不持有股票那么利润就是0，所以dp[0][1] = 0;
【遍历顺序】i从1到n，最后求第n天不持有股票dp[n-1][0],在本题中，最终票必须卖出
*/
五、打家劫舍问题
本博客是记录作者做动态规划算法的和打家劫舍相关的中等难度题的笔记。
| LeetCode题目 | 相关题目类型 | 题目类型分析 | 题目思路 | 相关链接 |
|---|---|---|---|---|
| 198 | 打家劫舍（中等难度） | 一排有不同金额的房屋，相邻房屋不能偷，求能偷的最大金额 | dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]，决定dp[i]的因素就是第i房间偷还是不偷。 | 198. 打家劫舍 - 力扣（LeetCode） (leetcode-cn.com) |
| 213 | 打家劫舍II（中等难度） | 一圈有不同金额的房屋，相邻房屋不能偷，求能偷的最大金额 | 当有多余两间房的时候：考虑首位相连问题。取了第一间房，就不能要最后一间房：[0, n-2] ； 取了最后一间房，就不能要第一间房：[1, n-1]；对这两段用普通的打家劫舍算法，再取这两段的最大值返回。 | 213. 打家劫舍 II - 力扣（LeetCode） (leetcode-cn.com) |
| 337 | 打家劫舍III（中等难度） | 二叉树形状的动态规划，父子节点不能同时偷 | 偷当前节点,左右孩子就都不能偷，偷当前节点，左右孩子可以偷也可以不偷；递归函数返回一个长度为2的数组，0：不偷，1：偷 | 337. 打家劫舍 III - 力扣（LeetCode） (leetcode-cn.com) |
198. 打家劫舍
这道题目非常好理解，其求最大金额，在盗窃时存在多种方案，所以才会有最大金额。
以[1,2,3,1]为例，为了不触发警报，小偷可以选择1，3和2，1，比较其谁更大就选择谁
假设dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。，显然
决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
代码如下：
/*这道题目非常好理解，其求最大金额，在盗窃时存在多种方案，所以才会有最大金额。
以[1,2,3,1]为例，为了不触发警报，小偷可以选择1，3和2，1，比较其谁更大就选择谁
假设dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。显然
决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，
即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房（注意这里是考虑，并不是一定要偷i-1房）
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);*/
int rob(vector<int>& nums) {
if(nums.size()==1) return nums[0];
vector<int> dp(nums.size());//dp[i]表示加上第i个房屋后一共可以盗窃的最大金额
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
// 推导dp数组
for(int i=2;i<nums.size();i++){
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[nums.size()-1];
}
213. 打家劫舍 II
这道题目的关键是明白 第n个台阶只能从第n-1或者n-2个上来，所以到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法。
/*这道题目的关键是明白
思路如下：
1. 当只有一间房的时候，直接返回这个返回金额。
2. 当有两间房的时候，返回这两个房间的最大值。
3. 当有多余两间房的时候：考虑首位相连问题。
取了第一间房，就不能要最后一间房：[0, n-2]
取了最后一间房，就不能要第一间房：[1, n-1]
对这两段用普通的打家劫舍算法，再取这两段的最大值返回。
*/
int rob(vector<int>& nums){
if(nums.size()==1) return nums[0];
int result1 = robRange(nums, 0, nums.size() - 2); // 取了第一间房，就不能要最后一间房：[0, n-2]
int result2 = robRange(nums, 1, nums.size() - 1); // 取了最后一间房，就不能要第一间房：[1, n-1]
return max(result1, result2);
}
int robRange(vector<int>& nums, int start, int end) {
if (end == start) return nums[start];
vector<int> dp(nums.size());//动归数组
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 - 2] + nums[i], dp[i - 1]);
}
return dp[end];
}
337. 打家劫舍 III
整理后的代码如下：
// 长度为2的数组，0：不偷，1：偷
vector<int> robTree(TreeNode* cur) {
if (cur == NULL) return vector<int>{0, 0};
vector<int> left = robTree(cur->left);
vector<int> right = robTree(cur->right);
// 偷当前节点,左右孩子就都不能偷
int val1 = cur->val + left[0] + right[0];
// 不偷当前节点，左右孩子可以偷也可以不偷
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};
}
int rob(TreeNode* root) {
vector<int> result = robTree(root);
return max(result[0], result[1]);
}
六、剪绳子问题
343. 整数拆分（中等难度）
剑指 Offer 14- I. 剪绳子（中等难度）
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
点评
class Solution {
public:
/*解析：本题是将一个整数n拆分成若干个数字之和，并且使这几个数字之积最大
分析：
结论1：至少剪下长度为2的绳子
对任意长度n的绳子都不应该剪下长度为1的绳子，因为1和任何数相乘都是哪个数本身：n>(n-1)*1
结论2：求长度为n的绳子剪掉后的最大乘积与求长度为n-1、n-2、n-3的绳子的最大乘积的思路一致
本题是求最优解问题，如乘积最大，该问题可以划分为若干子问题，例如剪一刀后，剩余剪的问题和之前性质一致
【状态定义】：dp[i] 表示长度为i的绳子剪成m段后的最大乘积
【转移方程】：
假设剪一刀，绳子变为2段，第一段是长度为j，第二段的长度为i-j，其乘积为j*(i-j)，2<=j<n
那么要不要继续剪第二刀或者第三刀呢？不确定
如果不剪的话，总的乘积就是j*(i-j)
如果剪的话，不清楚剪几刀，索性第二段的最大乘积表示为dp[i-j]，总的乘积为j*dp[i-j]
那么最终剪不剪，取决于最大值:
则本次剪的最大乘积为max(j*(i-j),j*dp[i-j]);2<=j<i
由于j的取值需要遍历，即不清楚第一刀j是多少，只能保留最大值
dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));//第一刀剪j-1和第一刀剪i之间取足底啊之
【初始状态】：
首先考虑边界问题，已知绳子最少应该剪下长度为2的的小段，那么长度为1、2的绳子就是边界问题
绳子必须被剪一刀，所以绳子为2时，其只能是分成1和1
dp[2]=1;
*/
int cuttingRope(int n) {
if(n<=1) return 1;//实际上测试数据中n>=2
vector<int> dp(n+1,0);//动规数组，dp[i] 表示长度为i的绳子剪成m段后的最大乘积
dp[2]=1;//长度为2的绳子只能剪成1和1，所以最大乘积是1
// 推导长度为[3,n]的绳子的最大乘积
for(int i=3;i<=n;i++){
// 剪第一刀，分为j和i-j，j的大小应该在[2,i）
for(int j=2;j<i;j++){
// 如果不剪，乘积为j*(i-j)，如果继续剪更多刀，乘积为j*dp[i-j]
int temp=max(j*(i-j),j*dp[i-j]);// 第一刀剪j的最大乘积
dp[i]=max(dp[i],temp);//绳子为i的最大乘积，j不同情况下的最大值
}
}
return dp[n];
}
};
剑指 Offer 14- II. 剪绳子 II（中等难度）
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
点评
class Solution {
public:
/*解析：本题是将一个整数n拆分成若干个数字之和，并且使这几个数字之积最大
和[剑指 Offer 14- I. 剪绳子（中等难度）]的区别在于n的测试数据变得更大，需要对答案取模。
C++中取余之后max函数就不能用来比大小，不可以继续使用动态规划法,难点在于大数运算
经过数学推导可知：
① 当所有绳段长度相等时，乘积最大。
② 最优的绳段长度为 3 。
用贪心的思想，尽可能地多切出点长度为3的绳子，对于最后的切法，要考虑到整体长度：
（1）如果绳子长度为2，切1和1，返回1
（2）如果绳子长度为3，切2和1，返回2
（3）如果绳子长度为4，切2和2，返回4
（4）如果身子长度大于4，
（1）如果绳子长度为3的倍数，全部切3，剩余0
（2）如果绳子长度为3的倍数+1，则切若干3，剩余4
（3）如果绳子长度为3的倍数+2，则切若干3，剩余2
*/
int cuttingRope(int n) {
if(n<=3) return n-1;//实际上测试数据中n>=2
long res = 1;// 乘积
// 将n减去若干个3，直至n<=4,n=2、3、4
while (n > 4) {
n -= 3;
res *= 3;
res %= 1000000007;
}
// 乘以剩余段长
res=res * n % 1000000007;
return res;
}
};
七、其他问题
1、二叉树问题
96. 不同的二叉搜索树（中等难度）
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。n的范围在[1,19]
输入：n = 3
输出：5
点评
class Solution {
public:
/*动态规划题
【状态定义】dp[i]表示i个节点的二叉搜索树的个数
【状态转换】以dp[3]为例，dp[3]=元素1为根的个数+元素2为根的个数+元素3为根的个数
元素1为根的个数=右子树有2个元素的个数*左子树有0个元素的个数=dp[2]*dp[0]
元素2为根的个数=右子树有1个元素的个数*左子树有1个元素的个数=dp[1]*dp[1]
元素3为根的个数=右子树有0个元素的个数*左子树有2个元素的个数=dp[0]*dp[2]
得dp[3]==dp[2]*dp[0]+dp[1]*dp[1]+dp[0]*dp[2]
假设j为根节点个数，范围在[1,i]
则 dp[i]+=元素j为根的个数
=右子树有i-j个元素的个数*左子树有j-1个元素的个数
=dp[i-j]*dp[j-1]
【初始状态】根据递推公式，dp[0]需要初始化
dp[0]表示0个节点的二叉搜索树的个数，可以视为空树，设为1
【遍历顺序】根据递推公式，dp[i]的推导依赖于j，dp[i-j]在dp[i]之前得出
所以i的范围是正序，在[1,n]，j不能超过i，范围在[1,n]
*/
int numTrees(int n) {
vector<int> dp(n + 1);
dp[0] = 1;
// i表示节点数,范围在[1,n]
for (int i = 1; i <= n; i++) {
// j表示j为根时的情况，范围在[1,i]
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];// 递归公式
}
}
return dp[n];
}
};
95. 不同的二叉搜索树 II（中等难度）
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回所有满足题意的二叉搜索树。n的范围在[1,8]
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
点评
该题和96的不同点在于，其需要返回所有不同的二叉搜索树，其n的范围缩小到8，就减少了计算量，可以用深度优先搜索。96中的动态规划无法用来求解该题。
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
return dfs(1, n);
}
vector<TreeNode*> dfs(int start,int end){
if(start>end) return {nullptr};
vector<TreeNode*> resTrees;
// 遍历所有为n的节点，作为当前的根节点
for(int i=start;i<=end;++i){
// 获得所有可行的左子树集合
vector<TreeNode*> leftTrees = dfs(start, i - 1);
// 获得所有可行的右子树集合
vector<TreeNode*> rightTrees = dfs(i + 1, end);
// 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
for (auto& left:leftTrees) {
for (auto& right:rightTrees) {
TreeNode* currTree = new TreeNode(i);
currTree->left = left;
currTree->right = right;
resTrees.emplace_back(currTree);//加入当前节点
}
}
}
return resTrees;
}
};
2、丑数问题
剑指 Offer 49. 丑数（中等难度）
264. 丑数 II（中等难度）
class Solution {
public:
/* 解析：本类型题是动态规划问题，属于特殊情景类，根据题意设计算法
【状态定义】：dp[i]表示的含义为从小到大排序的第i个丑数
【转移方程】：
理论原理：
最小的丑数是1，即dp[1]=1，那么如何得到其他的丑数呢？
任意一个丑数都是由小于它的某一个丑数*2，*3或者*5得到的，假设存在3个有序数组分别是每个丑数*2，*3或者*5
那么所有丑数的排列，必定就是上面ABC3个有序数组的合并结果然后去重得到的
假设有3个有序数组A={1*2}，B={1*3}，C={1*5}，定义三个指针，p2,p3,p5分别指向其中第一个元素。
dp[2]=min(A[p2],B[p3],C[p5])=2;
A={1*2,2*2}，B={1*3,2*3}，C={1*5,2*5}...
可以发现，ABC三个数组实际上就是dp[]*2，dp[]*3和dp[]*5的结果，
dp[i]=min(A[p2],B[p3],C[p5]),谁的最小就移动谁的指针
合并有序数组的一个比较好的方法，就是每个数组都对应一个指针，
然后比较这些指针所指的数中哪个最小，就将这个数放到结果数组中，然后该指针向后挪一位。
*/
int nthUglyNumber(int n) {
vector<int> dp(n+1,0);//动规数组
dp[1]=1;//初始状态
int p2=1,p3=1,p5=1;//三个指针中的初始值
// 遍历[2,n]
for(int i=2;i<=n;i++){
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = min(min(num2, num3), num5);//取三个有序数组中的最小值
// 谁的最小谁的指针就移动（合并3个有序数组的操作）
if (dp[i] == num2) p2++;
if (dp[i] == num3) p3++;
if (dp[i] == num5) p5++;
}
return dp[n];
}
};
3、约瑟夫环问题
剑指 Offer 62. 圆圈中最后剩下的数字（简单难度）
class Solution {
public:
/* 本题是根据经典的约瑟夫环的数学问题设计而来的，
N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
解决方案：
模拟法：普通的模拟方式就是使用循环链表，按照题意进行模拟，其时间复杂度高达O(nm)
动态规划法：
【状态定义】：dp[i] 表示的含义为有i个数，每次删除第m个数后的剩余数字索引,i<n
【转移方程】：假设有8个数，每次删除第3个数：
索引：0 1 2 3 4 5 6 7
1 2 [3] 4 5 6 7 8
4 5 [6] 7 8 1 2
7 8 [1] 2 4 5
2 4 [5] 7 8
7 8 [2] 4
4 7 [8]
[4]7
7 最终的胜利者
通过观察上述过程，可知，每删除一个数字，相当于将胜利者的索引前移了m位
已知i-1个人时，胜利者的下标位置dp[i-1]
i个人时，胜利者的索引相当于往后移动M位，由于移动后数组可能越界，
如果超出，则超出的部分接到头部，索引则需要对数字个数i取模
dp[i]=(dp[i-1]+m)%i，
【初始状态】： dp[1] = 0
*/
int lastRemaining(int n, int m) {
vector<int> dp(n+1,0);
dp[1]=0;
for (int i = 2; i <=n; i++) {
dp[i]=(dp[i-1]+m)%i;
}
return dp[n];
}
};
4、乘积数组
剑指 Offer 66. 构建乘积数组（中等难度）
238. 除自身以外数组的乘积（中等难度）
class Solution {
public:
/*解析：本题的题意不难理解，最简单的思路就是用2个循环暴力破解
但是注意到a的长度最多100000，而且不让用除法，所以暴力破解法大概率会超时。
*/
vector<int> constructArr(vector<int>& a) {
// 方法一：暴力破解法（超时）
// int n=a.size();
// vector<int> res(n,1);
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// if(j!=i) res[i]*=a[j];
// }
// }
// return res;
// 方法二：
int n=a.size();
vector<int> res(n,1);
int left=1;
for(int i=0;i<n;i++){
res[i]=left;
left*=a[i];
}
int right=1;
for(int i=n-1;i>=0;i--){
res[i] *= right;
right *= a[i];
}
return res;
}
};
152. 乘积最大子数组（中等难度）
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
点评
首先假设存在某个最大乘积，然后对数组遍历，在经过每个元素的时候，有以下四种情况：
- 如果该元素为正数：
- 如果到上一个元素为止的最大乘积也是正数，那么直接乘上就好了，同样的最大乘积也会变得更大
- 如果到上一个元素为止的最大乘积是负数，那么最大乘积就会变成该元素本身，且连续性被断掉
- 如果该元素为负数：
- 如果到上一个元素为止的最大乘积也是负数，那么直接乘上就好了，同样的最大乘积也会变得更大
- 如果到上一个元素为止的最大乘积是正数，那么最大乘积就会不变，且连续性被断掉
以上四种情况中说到的最大乘积都是临时最大乘积，每遍历新的元素都需要进行比较来确定真正的最大乘积。
如果细心的话就可以发现，如果要得到乘以当前元素以后的最大乘积，需要记录最大乘积，也要记录最小乘积，因为最小值可能翻身变最大值。
class Solution {
public:
/* 找出最大乘积子序列，子序列必须连续
该题的难点在于序列中存在负数，在乘积中会让原来最大的变最小的，最小的变最大的
注意和53题区分
（1）假设不存在负数，imax表示i之前的最大乘积,对于nums[i],分2种情况讨论：
如果乘nums[i],那么imax = imax*nums[i];
如果不乘nums[i],那么由于子序列的连续性,之前的子序列不能再使用,
i作为新的子序列中的第一个数,重新计算乘积imax = nums[i];
综合,imax = max(imax*nums[i], nums[i]);
（2）由于存在负数，nums[i]<0时,会让之前的连续子序列最小乘积（负数）变为最大值
所以需要同时维护一个最小乘积：imin = min(imin*nums[i], nums[i]);
当nums[i]<0时，交换imin 和imax 的值
*/
int maxProduct(vector<int>& nums) {
int n=nums.size();
int maxRes = INT_MIN;
int imax = 1, imin = 1;// 保存最大值和最小值
for(int i=0; i<n; i++){
// 如果当前数是负数,在乘积中会让原来最大的变最小的，最小的变最大的
if(nums[i]<0) swap(imax, imin);
imax = max(imax*nums[i], nums[i]);// 记录此时的最大值
imin = min(imin*nums[i], nums[i]);// 记录此时的最小值，辅助
maxRes = max(maxRes, imax);// 保存最大值
}
return maxRes;
}
};
5、骰子问题
剑指 Offer 60. n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
点评
class Solution {
public:
/* 解析：每个骰子可以投出1-6个数，n个骰子的点数和的范围为[n,6n].
如果采用暴力统计方式，则需要遍历6^n个组合，统计出每个点数和的次数/6^n，显然运算非常大。
第1个骰子投出的每个点数的概率相等，均为1/6，
第2个骰子投出后，会影响之前已投出的每个点数的概率
【状态定义】：dp[i][s] 表示i个骰子投出s点的次数
【状态转移】：
第i个骰子会投出[1,6]点，则第i-1个骰子需要投出[s-1,s-6]点，就可以使第i个骰子投出s点
dp[i][s]=dp[i-1][s-1]+dp[i-1][s-2]+dp[i-1][s-3]+dp[i-1][s-4]+dp[i-1][s-5]+dp[i-1][s-6]
【初始状态】：
1个骰子投出和为[1,6]的次数都是1，即
for (int i = 1; i <= 6; i++) dp[1][i] = 1;
*/
vector<double> dicesProbability(int n) {
//【状态定义】：dp[i][s] 表示i个骰子投出s点的次数，i的范围是[1,n],s的范围是[n,6n]
vector<vector<double>> dp(n+1,vector<double>(6*n+1,0));
//【初始状态】：1个骰子投出和为[1,6]的次数都是1
for (int i = 1; i <= 6; i++) dp[1][i] = 1;
// i 表示骰子数,
for (int i = 2; i <= n; i++) {
// s 表示 i 个骰子投出的点数
for (int s = i; s <= 6 * i; s++) {
// cur 表示第 i 个骰子投出的点数
for (int cur = 1; cur <= 6; cur++) {
// s - cur 表示前 i - 1 个骰子应该投出的点数
// 前 i - 1 个骰子投出的点数最小值为 i - 1
// 如果 s - cur 小于 i - 1 说明不可能
if (s - cur < i - 1) break;
dp[i][s] += dp[i - 1][s - cur];
}
}
}
double total = pow(6, n);// 总共的组合次数
// 点数和s取值[n,6n]，总共有 6n - n + 1 = 5n + 1个
vector<double> res(5 * n + 1);//表示点数和s为[n,6n]的概率：dp[n][i] / total
for (int i = n; i <= 6 * n; i++) res[i - n] = dp[n][i] / total;
return res;
}
};
6、正方形问题
221. 最大正方形（中等难度）
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
点评
方法一：暴力破解法
/* 方法一：暴力破解法：O(mnmin(m,n) ^2)
找到最大边长就是找到最大面积
遍历矩阵，遇到1就作为正方形左上角
根据左上角的坐标计算其最大边长
从该左上角出发进行遍历，如果都为1则扩大边长
*/
int maximalSquare(vector<vector<char>>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
int maxSide=0;// 最大边长
// 遍历整个矩阵
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
// 遇到一个1作为正方形的左上角,就更新当前最大边
maxSide = max(maxSide, 1);
// 计算可能的最大正方形边长
int currentMaxSide = min(m-i, n-j);
// 遍历
for (int k=1; k<currentMaxSide; k++) {
// 判断新增的一行一列是否均为 1
bool flag = true;
if (matrix[i + k][j + k]=='0') {
break;
}
for (int m = 0; m < k; m++) {
if (matrix[i + k][j + m] == '0'||matrix[i + m][j + k]=='0') {
flag = false;
break;
}
}
if (flag) {
maxSide = max(maxSide, k + 1);
} else {
break;
}
}
}
}
}
int maxSquare = maxSide * maxSide;
return maxSquare;
}
方法二：动态规划法
/* 方法二：动态规划法：
【状态定义】dp[i][j]表示以(i,j)为右下角所能构成的最大正方形边长
【状态转移】dp[i][j]的推导需要判断matrix[i][j]的值
如果matrix[i][j]=='1'，并且i==0||j==0，dp[i][j] = 1;
如果i!=0||j!=0,那么dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
【初始状态】
*/
int maximalSquare(vector<vector<char>>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
int maxSide=0;// 最大边长
// 遍历整个矩阵
vector<vector<int>> dp(m,vector<int>(n,0));
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
// 如果当前元素是1
if (matrix[i][j]=='1') {
// 如果是第一行或者第一列，那么 dp[i][j] = 1;
if (i==0||j==0) {
dp[i][j] = 1;
}
else {
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
}
maxSide = max(maxSide, dp[i][j]);
}
}
}
int maxSquare = maxSide * maxSide;
return maxSquare;
}
7、字符串匹配问题
剑指 Offer 19. 正则表达式匹配（困难难度）
10. 正则表达式匹配（困难难度）
class Solution {
public:
/* dp五部曲:
设原始串s的长度为m,模式串p的长度为n
注意定义:'*'表示它前面的(一个)字符可以出现任意次（含0次）!注意是一个
1.状态定义:设dp[i][j]为考虑s[0,i-1],p[0,j-1]时,是否能匹配上,匹配上就为true
2.状态转移:
2.1 p[j-1]为非'*'
2.1.1 若p[j-1]==s[i-1](必定为'a'-'z'),继续看dp[i-1][j-1]
2.1.2 若p[j-1]为'.',直接看dp[i-1][j-1]
2.2 p[j-1]为'*'
2.2.1 若p[j-2]==s[i-1](必定为'a'-'z'),则继续向前看dp[i-1][j]
因为对于p[0,j-1]来说,s[i-1]是冗余匹配可以由p[j-2]*补充
2.2.2 p[j-2]为'.',则'.'匹配了s[i-1],可以继续往前看dp[i-1][j]
注意这里是".*"的情形,也就是"万能串",生成"......"可以匹配任何非空s
2.2.3 此时p[j-2]为'a'-'z',且p[j-2]!=s[i-1],"p[j-2]*"直接废掉,看dp[i][j-2]
其中2.1.1和2.1.2可以合并为一种情形;2.2.1和2.2.2可以合并为一种情形
3.初始化:
3.1 空的p
3.1.1 可以匹配空的s,dp[0][0]=true
3.1.2 不可以匹配非空的s,dp[i][0]=false,i∈[1,m-1]
3.2 空的s
3.2.1 可以匹配空的s,dp[0][0]=true
3.2.2 可能可以匹配非空的p,要经过计算如"a*b*c*"
3.3 非空的p与非空的s,要经过计算
4.遍历顺序:显然是正序遍历
5.返回形式:直接返回dp[m][n]就表示考虑s[0,m-1],j[0,n-1]是否能匹配上
*/
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
// 定义动态规划数组
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
dp[0][0] = 1;
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
// 空的p的情形,dp[0][0]=true;其余为false
if(j==0) dp[i][j] = i == 0;
// 非空的p都是要经过计算的,此时j>=1
else {
// 2.1
if(p[j-1]!='*') {
if(i >=1&& (p[j-1]==s[i-1] ||p[j-1] == '.')) {
dp[i][j] = dp[i-1][j-1];// 本次匹配成功，继承上次匹配结果
}
}
// 2.2 ：p[j-1]和p[j-2]组成c=x*去匹配s[i-1]
else if(p[j-1]=='*') {
// s中存在可以匹配p的c的情形(2.2.1与2.2.2)
if(i>=1&&j>=2&&(p[j-2]==s[i-1]||p[j-2] == '.')) {
//p不动s向前一位，相当于用p匹配少一位的s
dp[i][j] = dp[i-1][j];
}
// s中不存在可以匹配p的c的情形(2.2.3)，则将c看做不存在
// 此时p[j-2]为'a'-'z',且p[j-2]!=s[i-1],"p[j-2]*"直接废掉
if(j >= 2) {
// s不变p向前2位
dp[i][j] = dp[i][j]||dp[i][j - 2];
// 这里用|=的原因是:2.2中满足任意一种情形就可以判定dp[i][j]=true
}
}
}
}
}
return dp[m][n];
}
bool isMatch2(string s, string p) {
int m = s.size();
int n = p.size();
// 定义一个lambda函数（匿名函数）
auto matches = [&](int i,int j) {
if(i==0) return false;// 如果s为空，恒为false
else if(p[j-1]=='.') return true; //如果p匹配字符为.,恒为true
else return s[i-1]==p[j-1];// 真长匹配
};
// 定义动态规划数组
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
dp[0][0]=true;
for(int i=0; i<=m; ++i) {
for(int j=1; j<=n; ++j) {
// 如果当前字符是'*'
if(p[j-1] == '*') {
if(matches(i,j-1)) dp[i][j] =dp[i-1][j]||dp[i][j-2];
else dp[i][j]=dp[i][j-2];
}
// 如果当前字符不是'*'
else{
if(matches(i,j)) dp[i][j] |= dp[i-1][j-1];
else dp[i][j]=false;
}
}
}
return dp[m][n];
}
bool isMatch1(string s, string p) {
int sLen=s.size();
int pLen=p.size();
// 空的p不可以匹配所有的s
//if(sLen!=0&&pLen==0) return false;
vector<vector<bool>> dp(sLen+1,vector<bool>(pLen+1));
dp[0][0]=true;// 空的p可以匹配空的s
// 匹配空串
for(int j=0;j<=pLen;j++){
if(p[j]=='*'&&dp[0][j-1])
dp[0][j+1]=true;
}
for(int i=0;i<sLen;i++){
for(int j=0;j<pLen;j++){
// 当前匹配成功，继承上次匹配结果
if(p[j]=='.'||p[j]==s[i]) dp[i+1][j+1]=dp[i][j];
// 如果p[j]是'*',
else if(p[j]=='*'){
// 如果上一个匹配字符匹配成功
if(p[j-1]=='.'||p[j-1]==s[i])
dp[i+1][j+1]=(dp[i][j+1]||dp[i+1][j-1]);
else dp[i+1][j+1]=dp[i+1][j-1];
}
}
}
return dp[sLen][pLen];
//return dp.back().back();
}
};
7、有向图问题
399. 除法求值（中等难度）
剑指 Offer II 111. 计算除法（中等难度）
class Solution {
public:
/* 本题可以看作是一个无向图问题，a/b=2,b/c=3，可以看作是一条a<->b<->c,其中a->b的权重是2，b->a的权重是1/2
该题目中说不存在矛盾的结果，即从a->b，不管中间经过几个节点，其权重乘积一定是不矛盾且唯一的，即最短路径就是唯一路径
可以根据图结构构建一个矩阵，然后使用Floyd算法求解最短路径*/
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
int nvars = 0;//
// 使用字典来给所有的变量标号
unordered_map<string, int> dict;// 用来给不同的变量编号
int n = equations.size();
for (int i = 0; i < n; i++) {
if (!dict.count(equations[i][0])) dict[equations[i][0]] = nvars++;
if (!dict.count(equations[i][1]) )dict[equations[i][1]] = nvars++;
}
// 构建一个二维矩阵来存储图结构
vector<vector<double>> graph(nvars, vector<double>(nvars, -1.0));
for (int i = 0; i < n; i++) {
// 获取一个变量对
int va = dict[equations[i][0]], vb = dict[equations[i][1]];
graph[va][vb] = values[i];// 正向为权重
graph[vb][va] = 1.0 / values[i];// 反向为1/权重
}
// 通过Floyd算法进行运算
for (int k = 0; k < nvars; k++) {
for (int i = 0; i < nvars; i++) {
for (int j = 0; j < nvars; j++) {
// graph[i][k]*graph[k][j]是因为该题中i->j的权重=i->k的权重*k->j的权重
if (graph[i][k] > 0 && graph[k][j] > 0) graph[i][j] = graph[i][k]*graph[k][j];
}
}
}
// 通过直接查询矩阵得到答案
vector<double> res;
for (const auto& q: queries) {
double result = -1.0;// 默认查不到
// 如果变量对都存在,则查询矩阵
if (dict.count(q[0]) && dict.count(q[1])) {
int ia = dict[q[0]], ib = dict[q[1]];
if (graph[ia][ib]>0) result = graph[ia][ib];
}
res.push_back(result);
}
return res;
}
};