9 动态规划-海口c网

9 动态规划

article/2025/7/5 6:57:00

9.3 爬楼梯

从1开始举例子发现规律

dp[i]=dp[i-1]+dp[i-2];

class Solution {
public:int climbStairs(int n) {if(n<=1){return 1;}vector<int>dp(n+1);dp[2]=2;dp[1]=1;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};

9.29 打家劫舍

1 确定dp数组下标与元素的含义

以当前元素结尾的能偷窃到的最多的钱

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==0) return 0;if(nums.size()==1)return nums[0];//1 dp数组含义：元素为以当前nums数组元素结尾的打家劫舍的最大值vector<int>dp(nums.size(),0);//3 初始化dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);//关键点：这个也是要符合下面的公式的 //dp[i]=max(dp[i-2]+nums[i],dp[i-1]);dp[i-2]不存在，nums[i]=nums[1]，dp[i-1]=dp[0]=nums[0]。//4 确定遍历方向for(int i=2;i<nums.size();i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);//2 递归公式}return dp[nums.size()-1];}
};

9.31 打家劫舍3

该题是动态二叉树

背过就好，最大的特点就是递归函数返回值类型为动态数组，里面包含了左或右节点偷还是不偷的时候的能取到的最大值。

class Solution {
public:int rob(TreeNode* root) {vector<int>result=rob1(root);return max(result[0],result[1]);}vector<int> rob1(TreeNode* root){if(root==nullptr){return vector<int>{0,0};//0：偷，1：不}vector<int>leftRob=rob1(root->left);vector<int>rightRob=rob1(root->right);//该层递归逻辑//偷该节点,那么左右节点都不能偷int cur0=root->val+leftRob[1]+rightRob[1];//关键点：root->val把该节点的值加上去//不偷该节点int cur1=max(leftRob[0],leftRob[1])+max(rightRob[0],rightRob[1]);return vector<int>{cur0,cur1};//递归函数的return写在递归逻辑里。}};

9.32 买卖股票的最佳时机

本题难点在分析dp递推公式和确定dp含义上

1 dp数组含义

dp[i][0] 表示第i天持有股票所得最多现金

dp[i][1] 表示第i天不持有股票所得最多现金

持有和买入不一样，今天持有也可能是昨天买入的

2 dp数组递推公式

dp[i][0]表示di天持有股票所得最多的现金，第i天持有股票有可能是今天买入的（-price[i]），也可能是昨天甚至前天、大前天、之前的某一天买入的（dp[i-1][0]），那就不变

dp[i][1] 表示第i天不持有股票所得最多现金，第一种情况，之前持有了股票但是今天卖出了（dp[i-1][0]+price[i]）第二种情况，根本没买（dip[i-1][1]）

dp[i][0] = max(dp[i - 1][0], -prices[i]);
//-prices[i]的真正形式应该是dp[i-1][1]-price[i]=0-prices[i],
//由于该题股票只能买卖一次，所以当从非持有状态转移到非持有状态时，用户的利润只能是-prices[i]，因为只能买卖一次，买之前用户的利润一定是0。
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

3 初始条件

dp[0][0]=-price[0]

dp[0][1]=0

4 确定遍历顺序

递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历

class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size()==0){return 0;}vector<vector<int>>dp(prices.size(),vector<int>(2));//0:持有，1：没持有dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<prices.size();i++){dp[i][0]=max(-prices[i],dp[i-1][0]);dp[i][1]=max(dp[i-1][0]+prices[i],dp[i-1][1]);}return dp[prices.size()-1][1];}
};

9.34 买卖股票的最佳时机2

该题股票可以买卖多次，

所以用户的状态为持有时（0），第一种情况：一直都是持有dp[i-1][0]，第二种情况：dp[i][0]可能是卖了又买的-prices[i]+dp[i-1][1]

dp[i][0] = max(dp[i - 1][0], dp[i-1][1]-prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

答案：

class Solution {
public:int maxProfit(vector<int>& prices) {int len=prices.size();vector<vector<int>>dp(len,vector<int>(2));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<len;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);//持有状态：1 原本就持有。2 上一个节点不持有（可能是之前的某个节点卖了）又在当前这个节点买的。dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);//非持有状态：1 原本不持有。2 上一个节点持有，在当前节点卖了}return dp[len-1][1];}
};

9.34 买卖股票的最佳时机（含冷冻期）

递推公式

//0：持有：1 上一个节点就持有，今天没买入 2 昨天不持有且非昨天卖出且今天买入 3昨天是冷冻期，今天买入 
//1：不持有(非今天卖出)：1 昨天就不持有且非昨天卖出今天不买 2 昨天是冷冻期，今天也没买入
//2：不持有(今天卖出)：1 昨天持有今天卖出
//3 ：冷冻期：1 原本就不持有且昨天卖出，今天啥也没干
// dp[i][0]=max(dp[i-1][0],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];

思路

class Solution {
public:int maxProfit(vector<int>& prices) {int len =prices.size();vector<vector<int>>dp(len,vector<int>(4,0));dp[0][0]=-prices[0];//0：持有：1 上一个节点就持有，今天没买入 2 昨天不持有且非昨天卖出且今天买入 3昨天是冷冻期，今天买入 //1：不持有(非今天卖出)：1 昨天就不持有且非昨天卖出今天不买 2 昨天是冷冻期，今天也没买入//2：不持有(今天卖出)：1 昨天持有今天卖出//3 ：冷冻期：1 原本就不持有且昨天卖出，今天啥也没干// dp[i][0]=max(dp[i-1][0],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];for(int i=1;i<len;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[len-1][1],max(dp[len-1][2],dp[len-1][3]));}
};

9.46 最大子序和

动态规划五步曲

1 确定dp[i]的元素和下标的含义

确定dp[i]的元素为以i为结尾的所有子序和的最大值

2 确定递推公式

两种情况，第一种就是当前遍历到的nums数组的元素加上dp[i-1]。第二种就是当前遍历到的nums数组的元素（为啥不是只有第一种情况呢？因为dp[i-1]有可能是负数）

3 初始化

由dp[i]的定义可知，dp[0]=nums[0];

4 确定遍历顺序

递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历

5 举例推导dp数组

9.52 回文子串

动态规划法：

递推公式思想：假设s[i]=s[j]，且[i+1, j-1]内的字符串是回文串，那么[i, j]内的字符串一定是回文串。

双指针法：

遍历整个字符串，

9.52 最长回文子序列

思路：

1 dp[i][j]数组元素的具体含义

字符串下标[i, j]里的最长回文串的长度

2 递推公式

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]);
}

3 初始化

for(int i=0;i<s.size();i++){dp[i][i]=1;
}

4 确定遍历顺序

i为竖坐标，j为横坐标

由下图可知，i从后往前遍历，j正好相反

i的遍历范围为（s.size()-2, 0）, j为（j+1, s.size()-1）

（对于该题，画画图，看出来遍历范围，直接写实际的遍历范围，不要全部遍历，否则极容易造成数组越界问题！！！）

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));for(int i=0;i<s.size();i++){dp[i][i]=1;}for(int i=s.size()-1 ;i>=0;i--){for(int j=i+1;j<s.size();j++){if(s[i]==s[j]){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=max(dp[i+1][j],dp[i][j-1]);}}}return dp[0][s.size()-1];}
};

2 找不到归属的

2.1 比特位数组

答案：

class Solution {
public:vector<int> countBits(int n) {vector<int>result;for(int i=0;i<=n;i++){result.push_back(compute(i));}return result;}int compute(int n){int i=0;while(n!=0){int m=n%2;if(m==1){i++;}n=n/2;}return i;}
};