动态规划的基础类题目
- 斐波那契数列
- 背包问题
- 爬楼梯
- ……
- 股票问题
- 子序列问题
使用动态规划解题时需要注意的点:
1.DP数组的定义和下标的含义
2.递推公式
3.DP数组的初始化
4.遍历顺序
5.打印DP数组
动态规划的尝试
- 题解:
第n级台阶有几种走法,只与第n-1级和第n-2级有关
1.dp数组:dp[i]表示到达i级台阶有dp[i]种方法,
2.递推公式:dp[i] = dp[i-1] + dp[i-2],
3.dp数组的初始化:dp[0] = 1, dp[1] = 1,
4.遍历顺序:从第n级台阶开始。
//直接使用dp数组
int climbStairs(int n) {
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
//节省部分空间开销的写法
int climbStairs(int n) {
int dp1 = 1;
int dp2 = 1;
int dp = 0;T
for (int i = 2; i <= n; i++) {
dp = dp1 + dp2;
buffer = dp2;
dp2 = dp1;
dp1 = dp;
}
return dp;
}
- 题解:
- dp数组:dp[i]表示到达i房间时,最大盗取金额,
- 状态方程:dp[i] = max(dp[i-2] + nums[i], dp[i-1]),意思是,在到达i房间时偷不偷取决于是在这偷了赚的多还是在上一间偷了赚的多,在这一间偷了,赚的钱表示为dp[i-2] + nums[i],在这一间没偷,赚的钱表示为dp[i-1],
- dp数组的初始化:dp[0] = 0, dp[1] = nums[0],
- 遍历顺序:从第1房间开始。
int rob(vector<int>& nums) { int dp[nums.size()]; 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]; }
- 题解:
- dp数组:dp[i]表示到达i房间时,最大盗取金额,
- 状态方程:dp[i] = max(dp[i-2] + nums[i], dp[i-1]),意思是,在到达i房间时偷不偷取决于是在这偷了赚的多还是在上一间偷了赚的多,在这一间偷了,赚的钱表示为dp[i-2] + nums[i],在这一间没偷,赚的钱表示为dp[i-1],
- dp数组的初始化:这是本题与上题区别较大的地方,在上题中,我们默认在第一间房间偷不偷只取决于在第二间房偷不偷,在这题中,在第一间房偷不偷取决于在最后一间房偷不偷和在上一间房偷不偷,从dp[2]到dp[n-1]的计算方式并不发生变化,存在两种情况,第一间房子不偷,此时最大金额为从第二间偷到第n间的最大金额,最后一间房子偷,此时最大金额为从第一间偷到第n-1间的最大金额,
- 遍历顺序:从第1房间开始。
int rob(vector<int>& nums) {
if(nums.size() <= _0) {
auto max = max_element(nums.begin(), nums.end());
return *max;
}
int dp[nums.size()-1];
dp[0] = nums[0];
dp[1] = max(nums[1], nums[0]);
//从1偷到n-1
for (int i = 2; i < nums.size()-2; i++) {
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
if(i == nums.size()-1){
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
}
int dp1 = dp[nums.size()-1];
dp1[0] = nums[1];
dp1[1] = max(nums[1], nums[2]);
//从2偷到n
for (int i = 2; i < nums.size()-2; i++) {
dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i+1]);
}
return max(dp[nums.size()-2], dp1[nums.size()-2]);
}
题解:
int maxProfit(vector<int>& prices){
int len = prices.size();
if(len <= 1){
return 0;
}
int f0 = -prices[0];
int f1 = 0;
int f2 = 0;
for(int i = 0; i<len; i++){
int newf0 = max(f0, f2-prices[i]);
int newf1 = f0 + prices[i];
int newf2 = max(f2, f1);
f0 = newf0;
f1 = newf1;
f2 = newf2;
}
return max(f1, f2);
}