使用最小花费爬楼梯
题目叙述：给定数组cost,cost[i]表示从楼梯第i个台阶向上爬需要支付的费用。一旦支付费用，可选择向上爬一个或两个台阶。你可以选择从下标为0或下标为1的台阶开始爬，求达到楼梯顶部的最低花费。
思路：dp[i]表示达到第i阶的最低花费，dp[0] = 0, dp[1] = 0,从第三项开始递推，每到第i阶都可以是从前一阶或前两阶爬上来的。
代码：
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int dp[cost.size()+10]; dp[0]=0,dp[1]=0; for(int i=2;i<=cost.size();i++){ dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); } return dp[cost.size()]; } };
不同路径
题目叙述：一个机器人位于一个m*n的网格的左上角，机器人每次只能向下或向右移动一步，机器人移动到网格右下角总共有多少条不同的路径。
思路：dp[i][j]表示从起点到位置(i,j)的不同路径数量，初始状态下，第一行和第一列只有一种路径（只能一直向右或向下走），双重循环递推，每到一个位置有两种方案，将两种方案累加。
代码：
class Solution { public: int uniquePaths(int m, int n) { int dp[110][110]; for(int i=0;i<m;i++) dp[i][0]=1; for(int i=0;i<n;i++) dp[0][i]=1; for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; } };
不同路径2
题目叙述：给定m*n的整数数组grid,从左上角尝试移动到右下角，每次只能向下或向右移动一步，网格中的障碍物和空位置分别用1和0表示，机器人移动路径中不能包含任何有障碍物的方格。求能到右下角的不同路径的数量。
思路：dp[i][j]表示从起点到位置(i,j)的不同路径数量，如果某位置是障碍物，则dp[i][j]=0,初始化第一行和第一列，只要遇到障碍物就停下。双重循环递推，只有当前不是障碍物才累加从上一步走到本步的方案数。
代码：
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m=obstacleGrid.size();//行 int n=obstacleGrid[0].size();//列 int dp[110][110]; memset(dp,0,sizeof(dp)); 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]==0){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } } return dp[m-1][n-1]; } };
整数拆分
题目叙述：给定整数n,将其拆解为k个正整数的和（k>=2）,并使得这些整数的乘积最大化，返回可以获得的最大乘积数。
思路：dp[i]表示将正整数i拆解后可以获得的最大乘积，初始条件dp[2]=1。对于每个i,尝试所有可能的第一个拆分数j（1 ≤ j ≤ i/2）,并考虑两种情况：j*(i-j):将i拆成两个数不再继续拆分，j*dp[i-j]：将i拆成两个数后继续拆分(i-j)部分。
代码：
class Solution { public: int integerBreak(int n) { vector<int> dp(n+1,0); dp[2]=1; for(int i=3;i<=n;i++){ for(int j=1;j<=i/2;j++){ int t1=j*(i-j); int t2=j*dp[i-j]; dp[i]=max(dp[i],max(t1,t2)); } } return dp[n]; } };
不同的二叉搜索树
题目叙述：给定整数n,求由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种。
思路：dp[i]表示用i个连续节点，可以构建的不同BST数量，初始状态下dp[0]=1。双重循环递推，第一重循环遍历1到n,第二重循环遍历1到i,表示1到i可以让每一个节点都做根节点，左子树包含节点 1 到 j-1，共有 j-1 个节点，对应的 BST 数量为dp[j-1],右子树包含节点 j+1 到 i，共有 i-j 个节点，对应的 BST 量为dp[i-j],因此，以 j 为根节点的 i 个节点的 BST 总数为左右子树数量的乘积dp[j-1] * dp[i-j]。
代码：
class Solution { public: int numTrees(int n) { vector<int> dp(n+10,0); 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]; } };
分割等和子集
题目叙述：给定只包含正整数的非空数组nums，请判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
思路：可转化为01背包问题。如果数组总和为奇数，则直接返回false,如果总和为偶数，则将问题转化为：从数组中选一些数，使其和等于总和的一半。dp[j]表示容量为j的情况下选出的最大价值。
代码：
class Solution { public: bool canPartition(vector<int>& nums) { int sum=0; for(int i=0;i<nums.size();i++) sum+=nums[i]; int target=sum/2; if(sum%2!=0) return false; vector<int> dp(target+10,0); for(int i=0;i<nums.size();i++){ for(int j=target;j>=nums[i];j--){ dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]); } } return dp[target]==target; } };
最后一块石头的重量2
1049. 最后一块石头的重量 II - 力扣（LeetCode）
题目叙述：有一堆石头,stones[i]表示第i块石头的重量。每一回合任意选两块石头将其粉碎，假设石头重量分别为x,y，x<=y，则粉碎结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头，返回此石头的最小可能重量，如果没有石头剩下，就返回0。
思路：同样是01背包问题。将石头分为两组，要让两组石头重量的累加和之差尽可能相等。再做转化，我们希望从石头中选出一部分，使其总和尽可能接近总重量的一半。
代码：
class Solution { public: int lastStoneWeightII(vector<int>& stones) { int sum=0; for(int i=0;i<stones.size();i++) sum+=stones[i]; int target=sum/2; 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]); } } return sum-2*dp[target]; } };
目标和
题目叙述：给定非负整数数组nums和整数target。向数组中的每个整数前添加+或-，然后串联起所有整数构造出一个表达式，返回可以用上述方法构造的运算结果为target的不同表达式数量。
思路：问题可以转化为01背包问题。假设添加+的数字集合其和为left，添加-的数字集合其和为right，则left-right=target,left+right=sum，再转化 2*left=sum+target，即left=(sum+target)/2。问题转化为从数组中选取一些数字，使得他们的和等于(sum+target)/2。
代码：
class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int sum=0; for(int i=0;i<nums.size();i++) sum+=nums[i]; if(sum<abs(target) || (sum+target)%2!=0) return 0; int left=(sum+target)/2; vector<int> dp(left+10,0); dp[0]=1; for(int i=0;i<nums.size();i++){ for(int j=left;j>=nums[i];j--){ dp[j]+=dp[j-nums[i]]; } } return dp[left]; } };
一和零
题目叙述：给定二进制字符串数组strs和两个整数m,n。找出strs的最大子集长度，该子集最多有m个0和n个1。
思路：可转化为二维背包问题，dp[i][j]表示使用i个0和j个1能获得的最大子集大小。遍历字符串数组，首先统计每个字符串中0和1的数量，之后二重循环递推，两重循环逆序遍历两种字符的数量。
代码：
class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { // dp[i][j] 表示使用 i 个 0 和 j 个 1 能获得的最大子集大小 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (const string& s : strs) { int zeros = 0, ones = 0; // 统计当前字符串中 0 和 1 的数量 for (char c : s) { if (c == '0') { zeros++; } else { ones++; } } // 逆序遍历背包容量，防止重复计算 for (int i = m; i >= zeros; --i) { for (int j = n; j >= ones; --j) { dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1); } } } return dp[m][n]; } };
零钱兑换2
题目叙述：给定整数数组coins表示不同面额的硬币，另给整数amount表示总金额。计算返回可以凑成总金额的硬币组合数。
思路: 完全背包问题。dp[i]表示凑成金额i的组合数，初始化dp[0]=1。使用当前金币coin来凑成金额j的组合数等于不使用coin凑成j的组合数加上使用coin凑成j-coin的组合数。
代码：
class Solution { public: int change(int amount, vector<int>& coins) { vector<long long> dp(amount+10,0); dp[0]=1; for(int i=0;i<coins.size();i++){ for(int j=coins[i];j<=amount;j++){ dp[j]+=dp[j-coins[i]]; } } return dp[amount]; } };
组合总数4
题目叙述：给出无重复数的整数数组nums和一个目标整数target。请从nums中找出并返回总和为target的元素组合的个数。
思路：同样是完全背包问题，注意我们要求的是排列数。dp[i]表示凑成总和为i的排列数,初始d[0]=1。双重循环递推，第一重循环遍历目标总和(容量)，第二重循环遍历数组中每个数字(物品)。只要当前数字没有超过容量，dp[j] += dp[j - num]表示要计算总和为 j 的排列数，我们可以把所有以 num 结尾的排列数加起来。
代码：
class Solution { public: int combinationSum4(vector<int>& nums, int target) { int n=nums.size(); vector<int> dp(target+10,0); dp[0]=1; for(int j=0;j<=target;j++){ for(int i=0;i<n;i++){ if(j-nums[i]>=0){ dp[j]+=dp[j-nums[i]]; } } } return dp[target]; } };
零钱兑换
题目叙述：给定coins数组表示不同面额的硬币，以及一个整数amount表示总金额。计算可以凑成总金额所需的最少硬币个数。
思路：dp[j]表示凑成金额j所需的最少硬币个数。初始化dp[0]=0,其他金额dp[j]=MAX假设无法凑成。两层循环递推，第一重循环遍历每个硬币，第二重循环遍历金额。对于每个硬币，如果不加这个硬币的金额已经凑齐，就将这个硬币加进去。
代码：
class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount+10,0x3f3f3f3f); dp[0]=0; for(int i=0;i<coins.size();i++){ for(int j=coins[i];j<=amount;j++){ if(dp[j-coins[i]]!=0x3f3f3f3f) { dp[j]=min(dp[j],dp[j-coins[i]]+1); } } } if(dp[amount]==0x3f3f3f3f){ return -1; } else { return dp[amount]; } } };
完全平方数
题目叙述：给定整数n,求和为n的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方。
思路：dp[i]表示和为i的完全平方数的最少数量。初始状态dp[0]=0,对于其他和，先假设其无法凑成。双重循环递推，第一重循环遍历物品(可能用到的平方数)，第二重循环遍历背包容量，对于每个物品有选和不选两种方案。
代码：
class Solution { public: int numSquares(int n) { vector<int> dp(n+1,0x3f3f3f3f); dp[0]=0; for(int i=1;i*i<=n;i++){ for(int j=i*i;j<=n;j++){ dp[j]=min(dp[j],dp[j-i*i]+1); } } return dp[n]; } };
单词拆分
题目叙述：给定字符串s和字符串字典wordDict，如果可以利用字典中出现的一个或多个单词拼接出s则返回true，单词可重复使用。
思路：dp[i]表示字符串s的前i个字符能否被成功拆分出来。初始下dp[0]=true,其余dp[i]=false。考虑dp[i],我们可以尝试在0到i-1之间找到一个分割点j，将字符串分割为两部分，如果满足前半部分能被拆分且后半部分本身就是词典中的词汇，则dp[i]为true。查找可引入哈希集合优化。双重循环递推，第一重循环遍历可能的字符串长度，第二重循环遍历可能的分割点，如果同时满徐两个条件，则当前长度可拆分。
代码：
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(),wordDict.end()); int n=s.size(); vector<bool> dp(s.size()+1,false); dp[0]=true; for(int i=1;i<=n;i++){ for(int j=0;j<i;j++){ if(dp[j] && wordSet.find(s.substr(j,i-j))!=wordSet.end()){ dp[i]=true; break; } } } return dp[n]; } };
打家劫舍
题目叙述：小偷计划偷沿街的房屋，每个房屋内藏有一定量的现金，如果相邻的房屋在同一晚上被小偷闯入，则系统报警。给定代表每个房屋存放金额的数组，求不触发报警装置的情况下，一夜能偷盗的最高金额。
思路：dp[i]表示从第0间到第i间能偷到的最高金额。到第i间房时，面临两个抉择，一个是偷这间房，不偷上一间房；另一个是不偷这间房，偷上一间房。初始状态下dp[0]=nums[0],dp[1]为第0间房和第一间房的最大值。
代码：
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()+10,0); dp[0]=nums[0]; dp[1]=max(nums[0],nums[1]); for(int i=2;i<nums.size();i++){ dp[i]=max(dp[i-1],dp[i-2]+nums[i]); } return dp[nums.size()-1]; } };
打家劫舍2
题目叙述：在上一题的基础上，现在所有房屋围成一个圈，求能偷到的最高金额。
思路：在上一题的基础上，抽取下标为[l,r]区间内能偷盗的最大金额。破换成链，头尾分别去掉得到两个结果取最大值。
代码：
class Solution { public: int rob(vector<int>& nums) { if(nums.size()==0) return 0; if(nums.size()==1) return nums[0]; return max(fun(nums,0,nums.size()-2),fun(nums,1,nums.size()-1)); } int fun(vector<int> &nums,int l,int r){ if(l==r) return nums[l]; vector<int> dp(nums.size()+10,0); dp[l]=nums[l]; dp[l+1]=max(nums[l],nums[l+1]); for(int i=l+2;i<=r;i++){ dp[i]=max(dp[i-1],dp[i-2]+nums[i]); } return dp[r]; } };
打家劫舍3
题目叙述：所有房屋的排列构成一颗二叉树，给定二叉树root，求不触发警报的情况下小偷能偷取的最高金额。
思路：对于每一个节点，dp[0]表示不偷当前节点，能从当前节点及其子节点获取的最大值，dp[1]表示偷当前节点能从当前节点及其子节点中获取的最大值。如果不偷当前节点，则他的左右节点可以自由选择偷或不偷，如果偷当前节点，其左右子节点都不能偷。
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int rob(TreeNode* root) { vector<int> res=robTree(root); return max(res[0],res[1]); } vector<int> robTree(TreeNode* cur){ if(cur==nullptr) return {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}; } };
买卖股票的最佳时机
题目叙述：price[i]表示一只股票第i天的价格。你只能在某一天买入这只股票然后在未来某一个不同的日子卖出股票，求你能获取的最大利润。
思路：dp[i][j]表示第i天持有和不持有此股票，此时的利润。初始化状态第一题持有股票和不持有股票此时的利润。开始递推，本天持有股票分两种情况：前一天就持有股票或当天买入股票，本天不持有股票分两种情况：前一天就不持有股票了或当天抛出股票。
代码：
class Solution { public: int maxProfit(vector<int>& prices) { int n=prices.size(); vector<vector<int>> dp(n+10,vector<int>(2,0)); dp[0][0]=0; //不持有 dp[0][1]=-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],-prices[i]); } return dp[n-1][0]; } };
买卖股票的最佳时机2
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
题目叙述：在上一题的基础上，可以在同一天多次买卖股票。
思路：在上一题的基础上，递推公式中，当天买入股票的情况下应是前一天不持有的情况下的累计利润-price[i]。
代码：
class Solution { public: int maxProfit(vector<int>& prices) { int n=prices.size(); vector<vector<int>> dp(n+10,vector<int>(2,0)); dp[0][0]=0; //第一天不持有 dp[0][1]=-prices[0]; //第一天持有 for(int i=1;i<prices.size();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][0]; } };
买卖股票的最佳时机3
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
题目叙述：在之前的基础上股价数组不变，限制最多可以完成两笔交易，并且必须在再次购买之前出售掉之前的股票，计算能获取的最大利润。
思路：两次交易限制，定义四状态DP数组表示在第i天两次持有和不持有。
代码：
class Solution { public: int maxProfit(vector<int>& prices) { int n=prices.size(); //dp[i][1] 第i天第一次持有 //dp[i][2] 第i天第一次不持有 //dp[i][3] 第i天第二次持有 //dp[i][4] 第i天第二次不持有 vector<vector<int>> dp(n+10,vector<int>(5,0)); dp[0][1]=-prices[0]; dp[0][2]=0; dp[0][3]=-prices[0]; dp[0][4]=0; for(int i=1;i<n;i++){ dp[i][1]=max(dp[i-1][1],-prices[i]); dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]); dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]); dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]); } return max(dp[n-1][2],dp[n-1][4]); } };
买卖股票的最佳时机4
188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
题目叙述：在3的基础上改为限制交易K次，给出能获取的最大利润。
思路：将一天的状态划分为2k个阶段，dp[i][j]表示第i天结束时处于第j个状态的利润最大值。j为奇数表示第某次持有状态，j为偶数表示第某次不持有状态。
代码：
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n=prices.size(); vector<vector<int>> dp(n+10,vector<int>(2*k+1,0)); //持有状态 for(int j=1;j<2*k;j+=2){ dp[0][j]=-prices[0]; } //不持有状态默认为0 for(int i=1;i<n;i++){ //天 for(int j=1;j<=2*k;j++){ //状态 if(j%2!=0){ //持有状态 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]); } else { dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]); } } } int res=-1; for(int j=2;j<=2*k;j+=2){ res=max(res,dp[n-1][j]); } return res; } };
买卖股票的最佳时机含冷冻期
309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）
题目叙述：price[i]表示第i天股票价格，可多次买卖，每次卖出股票后，无法在第二题买入股票（一天冷冻期），得出最大利润。
思路：四状态DP数组：dp[i][0] 持有股票，dp[i][1] 保持卖出股票状态（不是卖出日和冷冻期），dp[i][2] 当天卖出股票，dp[i][3] 处于冷冻期。
代码：
class Solution { public: int maxProfit(vector<int>& prices) { //dp[i][0] 持有股票 //dp[i][1] 保持卖出股票状态（今天不是卖出日和冷冻期） //dp[i][2] 当天卖出股票 //dp[i][3] 处于冷冻期 int n=prices.size(); vector<vector<int>> dp(n+10,vector<int>(4,0)); dp[0][0]=-prices[0]; dp[0][1]=0; dp[0][2]=0; dp[0][3]=0; for(int i=1;i<n;i++){ dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-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][1],dp[n-1][2],dp[n-1][3]}); } };
买卖股票的最佳时机含手续费
714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
题目叙述：price[i]表示第i天的股票价格，整数fee表示交易股票的手续费用，要求每笔交易需要付手续费，同样加在卖出它之前你就不能再继续购买股票的限制。
思路：dp[i][0]表示持有股票的状态，dp[i][1]表示不持有股票的状态。
代码：
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int n=prices.size(); vector<vector<int>> dp(n+10,vector<int>(2,0)); 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]; } };
最长递增子序列
题目叙述：给定整数数组nums，找出其中最长递增子序列长度。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
思路：dp[i]表示以nums[i]结尾的最长严格递增子序列的长度。为了求dp[i]，我么需要考虑i之前的所有元素j，如果i前面有更小的元素j，则nums[i]可以接在nums[j]后面，此时更新dp[i]=max(dp[j]+1,max)。最后在dp数组中找到最大值。
代码：
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); vector<int> dp(n,1); for(int i=1;i<n;i++){ for(int j=0;j<i;j++){ if(nums[j]<nums[i]){ dp[i]=max(dp[i],dp[j]+1); } } } int res=-1; for(int i=0;i<n;i++) res=max(res,dp[i]); return res; } };
最长连续递增序列
题目叙述：给定整数数组，找出最长且连续递增的子序列，返回子序列长度。
思路：dp[i]表示以nums[i]结尾的最长连续递增子序列的长度。对于每一个dp[i],我们只需要看其前一个元素nums[i-1]，如果前一个元素小于当前元素，则可将当前元素接在前一个元素后面，dp[i]=dp[i-1]+1。
代码：
class Solution { public: int findLengthOfLCIS(vector<int>& nums) { int n=nums.size(); vector<int> dp(n+10,1); for(int i=1;i<n;i++){ if(nums[i]>nums[i-1]) dp[i]=dp[i-1]+1; } int res=-1; for(int i=0;i<n;i++) res=max(res,dp[i]); return res; } };
最长重复子数组
题目叙述：给定两个数组，返回两个数组中公共的，长度最长的子数组的长度。
思路：dp[i][j]定义为以nums1[i-1]结尾和以nums2[j-1]结尾的公共子序列的最大长度。如果nums[i-1]==nums[j-1]，则两个元素可构成公共子数组的最后一个元素,dp[i][j]=dp[i-1][j-1]+1，如果两个元素不相等，则两个元素不能构成公共子数组的结尾，则dp[i][j]=0;
代码：
class Solution { public: int findLength(vector<int>& nums1, vector<int>& nums2) { int n1=nums1.size(); int n2=nums2.size(); vector<vector<int>> dp(n1+10,vector<int>(n2+10,0)); int res=-1; for(int i=1;i<=n1;i++){ for(int j=1;j<=n2;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; } };
最长公共子序列
题目叙述：给定两个字符串text1,text2，返回两个字符串的最长公共子序列的长度。
思路：定义dp[i][j]为字符串前i个字符和字符串前j个字符的最长公共子序列的长度。对于每个dp[i][j],如果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])。
代码：
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n1=text1.size(); int n2=text2.size(); vector<vector<int>> dp(n1+10,vector<int>(n2+10,0)); for(int i=1;i<=n1;i++){ for(int j=1;j<=n2;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[n1][n2]; } };
不相交的线
题目叙述：给定数组nums1,nums2，在两条独立的水平线上按给定的顺序写下nums1和nums2中的整数，连接两个数组nums[1]到nums[2]的直线，直线需要满足:nums1[i]==nums2[j]并且绘制的直线不与其他任何连线相交，以这种方式绘制线条，返回可以绘制的最大连线数。
思路：最长公共子序列模型，选中的数字相对顺序是一致的。
代码：
class Solution { public: int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) { int n1=nums1.size(); int n2=nums2.size(); vector<vector<int>> dp(n1+10,vector<int>(n2+10,0)); for(int i=1;i<=n1;i++){ for(int j=1;j<=n2;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[n1][n2]; } };
最大子数组和（DP解法）
题目叙述：给定整数数组nums，找出一个具有最大和的连续子数组，返回其最大和。
思路：本题可用贪心解法，下面给出DP解法：定义dp[i]为以nums[i]结尾的连续子数组的最大和。对于dp[i]我们只考虑dp[i-1]和nums[i]，我们可以选择将nums[i]加入到前面的子数组中，也可以让nums[i]自己成为一个新的子数组的开始。
代码：
class Solution { public: int maxSubArray(vector<int>& nums) { int n=nums.size(); vector<int> dp(n+10,0); dp[0]=nums[0]; for(int i=1;i<n;i++){ dp[i]=max(dp[i-1]+nums[i],nums[i]); } int res=-0x3f3f3f3f; for(int i=0;i<n;i++) res=max(res,dp[i]); return res; } };
判断子序列
题目叙述：给定字符串s,t，判断s是否是t的子序列。
思路：如果s是t的子序列，则两个字符串的最长公共子序列一定是s本身，只需计算LCS长度，然后判断是否等于s的长度即可。
代码：
class Solution { public: bool isSubsequence(string s, string t) { int n1=s.size(); int n2=t.size(); vector<vector<int>> dp(n1+10,vector<int>(n2+10,0)); for(int i=1;i<=n1;i++){ for(int j=1;j<=n2;j++){ if(s[i-1]==t[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[n1][n2]==s.size(); } };
不同的子序列
题目叙述：给定两个字符串s和t，统计返回在s的子序列中t出现的个数。
思路：问题转化为在s中能找出多少种子序列可以构成字符串t。dp[i][j] 表示 s前i个字符的子序列中，t前j个字符出现的个数。如果s[i-1] == t[j-1]，则说明两个字符可以匹配上，则可以选择用或不用s[i-1],如果不匹配，则只能跳过s[i-1]。
代码：
class Solution { public int numDistinct(String s, String t) { // 注意：s是源字符串，t是目标字符串 char[] t1 = s.toCharArray(); char[] t2 = t.toCharArray(); int n1 = s.length(); int n2 = t.length(); // dp[i][j] 表示 s前i个字符的子序列中，t前j个字符出现的个数 int[][] dp = new int[n1 + 1][n2 + 1]; // 1. 初始化：空字符串t是任何s的子序列，且只有一种方式 for (int i = 0; i <= n1; i++) { dp[i][0] = 1; } // dp[0][j] 默认为0，无需初始化 // 2. 状态转移 for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (t1[i - 1] == t2[j - 1]) { // 如果匹配，可以选择用或不用s[i-1] dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } else { // 如果不匹配，只能跳过s[i-1] dp[i][j] = dp[i - 1][j]; } } } // 3. 返回最终结果 return dp[n1][n2]; } }
两个字符串的删除操作
583. 两个字符串的删除操作 - 力扣（LeetCode）
题目叙述：给定两个字符串word1和word2，返回使得word1和word2相同的最小步数，每步可以删除任意一个字符串的任意一个字符。
思路：dp[i][j]表示使得word1的前i个字符和word2的前j个字符相等所需的最小删除步数。对于每个dp[i][j]，我们需要考虑word1的第i-1个字符和word2的第j-1个字符，如果两个字符相等则成功匹配，无需任何操作，如果两个字符不等，那么必须删除其中一个才能继续。
代码：
class Solution { public: int minDistance(string word1, string word2) { int n1=word1.size(); int n2=word2.size(); vector<vector<int>> dp(n1+10,vector<int>(n2+10,0)); for(int i=0;i<=n1;i++) dp[i][0]=i; for(int j=0;j<=n2;j++) dp[0][j]=j; for(int i=1;i<=n1;i++){ for(int j=1;j<=n2;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[n1][n2]; } };
编辑距离
题目叙述：给定两个单词word1和word2，返回将word1转为word2所使用的最少操作次数。你可以对一个单词执行如下操作：插入一个字符，删除一个字符，替换一个字符。
思路：dp[i][j]表示将word1的前i个字符转为word2的前j个字符所用的最少操作次数。考虑word[i-1]和word[j-1]，如果两个字符相等则成功匹配，无需任何操作。如果两个字符不相等，则字符不匹配，则必须选一种操作执行。
代码：
class Solution { public: int minDistance(string word1, string word2) { int n1=word1.size(); int n2=word2.size(); vector<vector<int>> dp(n1+10,vector<int>(n2+10,0)); for(int i=0;i<=n1;i++) dp[i][0]=i; for(int j=0;j<=n2;j++) dp[0][j]=j; for(int i=1;i<=n1;i++){ for(int j=1;j<=n2;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]+1,dp[i-1][j]+1,dp[i][j-1]+1}); } } } return dp[n1][n2]; } };
回文子串
题目叙述：给出一个字符串s,统计并返回这个字符串中回文子串的数目。
思路：dp[i][j]表示从索引i到j的子串是否是回文串。如果s[i]==s[j]，那么dp[i][j]的值取决于dp[i+1][j-1],如果s[i]!=s[j]，则s[i到j]不会是回文串。注意倒序遍历，递推过程中前面依赖于后面的dp值。
代码：
class Solution { public: int countSubstrings(string s) { int n=s.size(); vector<vector<bool>> dp(n,vector(n,false)); int res=0; //从下到上，从左到右 for(int i=n-1;i>=0;i--){ for(int j=i;j<n;j++){ if(s[i]==s[j]){ if(j-i<=1){ dp[i][j]=true; res++; } else if(dp[i+1][j-1]){ dp[i][j]=true; res++; } } } } return res; } };
最长回文子序列
题目叙述：给定字符串s,找出最长回文子序列并返回该序列长度。
思路：dp[i][j]表示从索引i到j的子串中，最长回文子序列长度。当s[i]==s[j]时，dp[i][j] = dp[i+1][j-1] + 2，当两个边界字符不相等时，必须放弃一个边界字符。同样倒序遍历。
代码：
class Solution { public: int longestPalindromeSubseq(string s) { int n=s.size(); vector<vector<int>> dp(n,vector<int>(n,0)); for(int i=0;i<n;i++) dp[i][i]=1; for(int i=n-1;i>=0;i--){ for(int j=i+1;j<n;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][n-1]; } };
