动态规划(Dynamic Programming)基础解析
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
509. 斐波那契数这道题目的变形版
class Solution {
public:
int climbStairs(int n) {
if(n<=1) return n;
vector<int> dp(n+1,0);
dp[1]=1;
dp[2]=2;
for(int i=3; i<=n; i++){
dp[i] = dp[i-1]+dp[i-2];
}return dp[n];
}
};
//递归法会超时
class Solution {
public:
int fib(int n) {
if(n<2) return n;
return fib(n-1)+fib(n-2);
}
};
746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> money(cost.size()+1);
money[0]=0;
money[1]=0;
for(int i=2; i<=cost.size(); i++){
money[i] = min(money[i-1]+cost[i-1], money[i-2]+cost[i-2]);//关键一步
}
return money[cost.size()];
}
};
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
class Solution {
public:
int uniquePaths(int m, int n) {
if(m==1&&n==1) return 1;
vector<vector<int>> path(m,vector<int>(n,0));
for(int i=0; i<m; i++) path[i][0]++;
for(int j=0; j<n; j++) path[0][j]++;
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
path[i][j]=path[i-1][j]+path[i][j-1];
}
}return path[m-1][n-1];
}
};
63. 不同路径 II
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {return 0;}
vector<vector<int>> path(m,vector<int>(n,0));
for(int i=0; i<m; i++){//初始化边界，上行和左列只要有障碍，障碍及后面都为0
if(obstacleGrid[i][0]==1){break;}
path[i][0] = 1;
}
for(int j=0; j<n; j++){
if(obstacleGrid[0][j]==1){break;}
path[0][j] = 1;
}
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
if(obstacleGrid[i][j]==1){path[i][j]=0;}
else{
path[i][j]=path[i-1][j]+path[i][j-1];
}
}
}return path[m-1][n-1];
}
};
343. 整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
class Solution {
public:
//分拆数字i，可以得到的最大乘积为dp[i]
int integerBreak(int n) {
vector<int> dp(n+1);
dp[2]=1;
for(int i=3; i<=n; i++){
for(int j=1; j<=i/2; j++){
dp[i]=max(dp[i], max(j*(i-j), j*dp[i-j]));
}
}return dp[n];
}
};
96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
**思路讲解：**以3个节点举例，dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
dp(n)=求和(左子树dp+右子树dp) ————根节点从1到n
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1);
dp[0]=1;
dp[1]=1;
for(int i=2; i<=n; i++){
for(int j=1; j<=i; j++){
dp[i]+=dp[j-1]*dp[i-j];
}
}return dp[n];
}
};
背包理论基础（二维数组实现）
#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];
}
// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
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]; j <= bagweight; 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]) 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数组实现
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 读取 M 和 N
int M, N;
cin >> M >> N;
vector<int> costs(M);
vector<int> values(M);
for (int i = 0; i < M; i++) {
cin >> costs[i];
}
for (int j = 0; j < M; j++) {
cin >> values[j];
}
// 创建一个动态规划数组dp，初始值为0
vector<int> dp(N + 1, 0);
// 外层循环遍历每个类型的研究材料
for (int i = 0; i < M; ++i) {
// 内层循环从 N 空间逐渐减少到当前研究材料所占空间
for (int j = N; j >= costs[i]; --j) {
// 考虑当前研究材料选择和不选择的情况，选择最大值
dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
}
}
// 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值
cout << dp[N] << endl;
return 0;
}
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
class Solution {
public:
//简化问题：因为是分割等和子集，所以要分割成两个子集
//就是用现有元素能否凑出和为sum/2的子集就可以了
//背包法，value=nums[i]; weight=nums[i]; bagsize=sum/2;
bool canPartition(vector<int>& nums) {
int n=nums.size();
int sum=0;
for(int i=0; i<nums.size(); i++){
sum+=nums[i];
}
if(sum%2!=0){return false;}
int target=sum/2;
vector<int> dp(target+1, 0);
for(int i=0; i<n; i++){
for(int j=target; j>=nums[i]; j--){
dp[j]=max(dp[j], dp[j-nums[i]]+nums[i]);
}
}
if(dp[target]==target){return true;}
return false;
}
};
1049. 最后一块石头的重量 II
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40]
输出：5
思路：转化问题：分成两堆石头重量和相差最小的，就是最小可能重量；转化为背包问题：target=sum/2,尽可能装满重量为target的石头，其重量为dp[target]。然后两堆石头重量分别为：dp[target]， sum-dp[target]；因为target=sum/2取整，所以sum-dp[target]>=dp[target]，所以答案为：(sum-dp[target])-dp[target]。
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-dp[target])-dp[target];
}
};
494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：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
示例 2：
输入：nums = [1], target = 1
输出：1
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
//肯定有leftsum-rightsum=target，且leftsum+rightsum=sum；所以leftsum=(target+sum)/2;
//那么就是求有多少种组合能够组成leftsum, 故bagsize=(target+sum)/2 (j)
//dp[i][j]：使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法
//递推公式为dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]
int n = nums.size();
int sum = 0;
for(int i=0; i<nums.size(); i++){
sum += nums[i];
}
int bagsize=(sum+target)/2;
if(abs(target)>sum) return 0;
if((sum + target) % 2 == 1) return 0;
vector<vector<int>> dp(nums.size(),vector<int>(bagsize+1,0));
if(nums[0]<=bagsize) dp[0][nums[0]]=1;//初始化最上行，dp[0][0]在第下面单独初始化
dp[0][0] = 1;
//如果前i个元素里面有numzero个0，那么就有2^numzero放法
int numzero=0;
for(int i=0; i<nums.size(); i++){
if(nums[i]==0) numzero++;
dp[i][0]=(int) pow(2.0, numzero);
}
for(int i=1; i<nums.size(); i++){
for(int j=0; j<=bagsize; j++){
if(nums[i]>j) {dp[i][j] = dp[i - 1][j];}
else {dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];}
}
}
return dp[n-1][bagsize];
}
};
一维动态数组解法
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size();
int sum = 0;
for(int i=0; i<nums.size(); i++){sum += nums[i];}
int bagsize=(sum+target)/2;
if(abs(target)>sum) return 0;
if((sum + target) % 2 == 1) return 0;
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];
}
};
474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1, vector<int>(n+1,0));
for(string str: strs){
int zeronum=0, onenum=0;
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];
}
};
518. 零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1, 0);
dp[0]=1;
for(int i=0; i<coins.size(); i++){
for(int j=coins[i]; j<=amount; j++){
if(dp[j]<INT_MAX-dp[j-coins[i]]){
//保证dp[j]=dp[j]+dp[j-coins[i]]中这个小于INT_MAX
dp[j]+=dp[j-coins[i]];
}
}
}return dp[amount];
}
};
注意：为什么不写成dp[i] + dp[i - nums[j]] < INT_MAX，这样先求和就会溢出报错，程序终止运行
| 写法 | 是否会溢出 | 原因 |
|---|---|---|
dp[i] + dp[i - nums[j]] < INT_MAX |
可能溢出 | 先计算 dp[i] + dp[i - nums[j]]，可能溢出 |
dp[i] < INT_MAX - dp[i - nums[j]] |
不会溢出 | 先判断 INT_MAX - dp[i - nums[j]]，再加法 |
377. 组合总和 Ⅳ
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：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)
请注意，顺序不同的序列被视作不同的组合。
注意：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1, 0);
dp[0]=1;
for(int i=0; i<=target; i++){
for(int j=0; j<nums.size(); j++){
if(i>=nums[j]&&dp[i]<INT_MAX-dp[i-nums[j]]){
dp[i]+=dp[i-nums[j]];
}
}
}return dp[target];
}
};
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
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]; j<=amount; j++){
if(dp[j-coins[i]]!=INT_MAX)
dp[j]=min(dp[j-coins[i]]+1, dp[j]);
}
}
if(dp[amount]==INT_MAX) return -1;
return dp[amount];
}
};
279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
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; j<=n; j++){
dp[j]=min(dp[j], dp[j-i*i]+1);
}
}
return dp[n];
}
};
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
//将wordDict里字符都映射在set里面
unordered_set<string> wordset(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; j<i; j++){
string word=s.substr(j, i-j);//从string里面截取单词
if(wordset.find(word)!=wordset.end() && dp[j]){
//如果wordset里面存在对应单词并且dp[j]=true
//dp[j]=true,说明s[0~j]是成立的可以组合的
//且word为s[j, i]是存在的字典里单词
//那么s[0~j + j~i]就是s[0~i]也是成立的
dp[i]=true;
}
}
}
return dp[s.size()];
}
};
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==1) return nums[0];
int n = nums.size();
vector<int> dp(n, 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[n-1];
}
};
213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
class Solution {
public:
// 这道题就分两种情况，情况1:第1位出发开始，不包含最后一位；
// 情况2:第2位出发开始，包含最后一位
int rob(vector<int>& nums) {
if(nums.size()==1) return nums[0];
int result1 = robfind(nums, 0, nums.size()-2); //情况1:第1位出发开始，不包含最后一位；
int result2 = robfind(nums, 1, nums.size()-1); // 情况2:第2位出发开始，包含最后一位
return max(result1, result2);
}
int robfind(vector<int>& nums , int begin, int end){
if(begin==end) return nums[begin];
vector<int> dp(nums.size());
dp[begin] = nums[begin];
dp[begin+1] = max(nums[begin], nums[begin+1]);
for(int i=begin+2; i<=end; i++){
dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[end];
}
};
337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
/**
* 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 vector<int>{0,0};
vector<int> left = robtree(cur->left);
vector<int> right = robtree(cur->right);
//要当前节点，不要左右子节点
int val1 = cur->val + left[1] + right[1];
//不要当前节点
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val1, val2};//第一个就是偷本节点，第二个是不偷本节点
}
};
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
//动态规划
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n==0) return 0;
vector<vector<int>> dp(n, vector<int>(2));
dp[0][0] -= prices[0];//
dp[0][1] = 0;
for(int i=1; i<prices.size(); i++){
dp[i][0] = max(dp[i-1][0], -prices[i]);//dp[i][0]获取最低价格股票
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]); //dp[i][1]寻找最高利润股票
}
return dp[n-1][1];
}
};
//贪心算法
class Solution {
public:
int maxProfit(vector<int>& prices) {
//贪心算法
int low = INT_MAX;
int result = 0;
for(int i=0; i<prices.size(); i++){
//可找例子推一下，这两步非巧妙，是在找到最小值后，再刷新最大值
low = min(low, prices[i]);
result = max(result, prices[i]-low);
}
return result;
}
};
122. 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：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 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n<=1) return 0;
vector<vector<int>> dp(n, vector<int>(2));
dp[0][0] = -prices[0];
dp[0][1] = 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][1];
}
};
//贪心算法
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> cha;
int res=0;
for(int i=1; i<prices.size(); i++){
cha.push_back(prices[i]-prices[i-1]);
}
for(int i=0; i<cha.size(); i++){
if(cha[i]>0){
res+=cha[i];
}
}return res;
}
};
123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
//太难了，一知半解
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()==0) return 0;
vector<vector<int>> dp(prices.size(),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][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 dp[prices.size()-1][4];
}
};
188. 买卖股票的最佳时机 IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
//上面买卖2次的扩展
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size()==0) return 0;
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2*k+1,0));
for(int i=1; i<dp[0].size(); i+=2){
dp[0][i] = -prices[0];
}
for(int i=1; i<prices.size(); i++){
for(int j=0; j<dp[0].size()-2; j+=2){
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i]);
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i]);
}
}
return dp[n-1][2*k];
}
};
309. 买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
//难度太大了
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<prices.size(); 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][1],max(dp[n-1][2],dp[n-1][3]));
}
};
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：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
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
class Solution {
public:
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<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]-fee);//卖出股票
}
return dp[n-1][1];
}
};
300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()<=1) return nums.size();
int res = 0;
vector<int> dp(nums.size(), 1);
for(int i=1; i<nums.size(); i++){
for(int j=0; j<i; j++){
if(nums[j]<nums[i]){
dp[i] = max(dp[i], dp[j]+1);
//j在(0,i)里面,只要dp[j]比dp[i]小，就存在递增子序列，即dp[j]+1
}
}
if(dp[i]>res){
res = dp[i];
}
}
return res;
}
};
674. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
//动态规划解法
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = 1;
for(int i = 1; i<nums.size(); i++){
if(nums[i]>nums[i-1]){
dp[i] = dp[i-1] + 1;
}
if(dp[i]>res){
res = dp[i];
}
}
return res;
}
};
//滑动窗口解法
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int res = 1;
int left = 0;
for(int right = 1; right<nums.size(); right++){
if(nums[right]>nums[right-1]){
res = max(res, right-left+1);
}else{
left = right;
}
}
return res;
}
};
718. 最长重复子数组
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
class Solution {
public:
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()+1; i++){
for(int j=1; j<nums2.size()+1; j++){
if(nums1[i-1]==nums2[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}
if(dp[i][j] > res){
res = dp[i][j];
}
}
}
return res;
}
};
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
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()];
}
};
1035. 不相交的线最长公共子序列变体版
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
nums1[i] == nums2[j]- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3
注意 ：这道题本质就是求最长公共子序列
class Solution {
public:
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()];
}
};
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size()==0) {return 0;}
vector<int> dp(nums.size(), 0);
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]);
if(dp[i]>res){
res = dp[i];
}
}
return res;
}
};
115. 不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
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()];
}
};
583. 两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco"
输出：4
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 i=0; i<=word2.size(); i++){dp[0][i]=i;}
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()];
}
};
72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
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], min(dp[i][j-1], dp[i-1][j-1]))+1;
//插入和删除是一样的，dp[i][j-1]+1或dp[i-1][j]+1
//替换元素dp[i-1][j-1]+1
}
}
}return dp[word1.size()][word2.size()];
}
};
647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
// 双指针法
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
for(int i = 0; i<s.size(); i++){
res+=find(s, i, i, s.size());//奇数个回文子串
res+=find(s, i, i+1, s.size());//偶数个回文子串
}
return res;
}
int find(string s, int i, int j, int n){
int res = 0;
while(i>=0 && j<n && s[i]==s[j]){
i--;
j++;
res++;
}
return res;
}
};
516. 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
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];
}
};