动态规划第二阶段第二课
🍬《糖果小怪兽——拿与不拿的选择》
🌟一、故事开始：夜晚的糖果街
1、在算法王国里，
有一条非常有名的街道：
🍭“糖果街”🍭
2、街道两边，
有很多很多糖果屋。
每个屋子里，
都藏着不同数量的糖果！
3、比如：
| 1 | 2 |
| 2 | 7 |
| 3 | 9 |
| 4 | 3 |
| 5 | 1 |
4、有一天，
一只小怪兽来到这里。
它特别爱吃糖！
😈“今天我要拿最多的糖果！”😈
5、但是！
糖果街有规则！
6、🚨规则：
如果拿了相邻的两间房，
你就违规了，所有糖果都会被收回
也就是说：
❌不能连续拿相邻房子的糖果
7、国王问：
🌟“小怪兽，你最多能拿多少糖果呢？”🌟
8、今天，
我们就来帮助小怪兽！
🌟二、先观察问题
1、糖果数量：
2 7 1 3 9
2、如果拿
2 + 1 + 9
得到：
12
3、如果：
拿
7 + 3
得到：
10
4、所以：
小怪兽说,答案应该是：
🌟12
5、对吗？
如果拿：
7 + 9
得到：
16
6、答案：
小怪兽说：是16
🌟三、动态规划真正的关键！
1、今天这个题，
和前面不一样。
2、因为：
这里出现了：
🌟“选”与“不选”！
3、以前：
只有一种推法。
4、今天：
每个房子：
都要做决定！
5、😵拿？
还是不拿？
🌟四、定义状态
1、我们定义：
dp[i]
表示：
“前i间房子，最多能拿多少糖果”
2、比如：
dp[3]
表示：
前3间房子：
2 7 9
最多能拿多少。
3、dp[5]
表示：
前5间房子，
最多能拿多少。
🌟五、分析最后一间房
1、动态规划最重要技巧：
🌟分析最后一步！
2、现在：
看第 i 间房。
小怪兽有两种选择：
🌟情况1：不拿第 i 间
那么：
答案就是：
前 i-1 间房子的最优答案
也就是：
dp[i-1]
🌟情况2：拿第 i 间
那么：
第 i-1 间不能拿！
所以：
答案变成：
前 i-2 间的答案 + 第 i 间糖果
也就是：
dp[i-2] + a[i]
🌟六、状态转移公式出现！
1、于是：
我们取最大值！
2、🌟状态转移：
dp[i] = max( dp[i-1] , dp[i-2]+a[i] )
3、🌟这就是：
🌟“选”与“不选”DP！
🌟七、初始化
1、假设：
a[1]=2
a[2]=7
2、那么：
（1）dp[1]
只有一间房。
所以：
dp[1] = a[1];
（2）dp[2]
两间房：
-
拿第1间
-
或拿第2间
取较大值。
（3）所以：
dp[2] = max(a[1], a[2]);
🌟八、手动画表
1、现在：
糖果：
2 7 1 3 9
2、我们开始填表。
| 1 | 2 | 2 |
| 2 | 7 | 7 |
| 3 | 1 | 7 |
| 4 | 3 | 10 |
| 5 | 9 | 16 |
3、🌟怎么来的？
dp[3]
不拿第3间：
dp[2] = 7
拿第3间：
dp[1] + 1 = 2 + 1 = 3
取最大：
7
dp[4]
不拿第4间：
7
拿第4间：
7 + 3 = 10
取最大：
10
dp[5]
不拿第5间：
10
拿第5间：
7 + 9 = 16
取最大：
16
🌟答案：
16
🌟九、参考代码
#include <iostream>
#include <algorithm>
using namespace std;
int a[105];
int dp[105];
int main()
{
int n;
cin >> n;
// 输入糖果数量
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
// 初始化
dp[1] = a[1];
dp[2] = max(a[1], a[2]);
// 状态转移
for(int i = 3; i <= n; i++)
{
dp[i] = max(dp[i – 1],
dp[i – 2] + a[i]);
}
cout << dp[n];
return 0;
}
🌟十、程序运行模拟
输入：
5
2 7 1 3 9
程序开始：
dp[1]=2
dp[2]=7
dp[3]
max(7, 2+1) = 7
dp[4]
max(7, 7+3) = 10
dp[5]
max(10, 7+9) =16
输出：
16
🌟十一、今天真正学会了什么？
1、今天这道题：
它第一次让我们学习：
🌟“决策DP”
2、什么意思？
每一步：
都要做决定！
3、比如：
拿？
还是不拿？
选？
还是不选？
这类DP：
特别特别多！
🌟十二、以后会遇到哪些类似题？
比如：
📚选作业
🎮选装备
🍎选水果
📦背包问题
🎯任务安排
很多问题：
都是：
🌟“选”与“不选”
🌟十三、动态规划四步法（再次强化）
🌟第一步：定义状态
dp[i]
表示：
前 i 间房子的最大糖果数。
🌟第二步：初始化
dp[1]
dp[2]
🌟第三步：状态转移
dp[i] = max(dp[i-1],dp[i-2]+a[i])
🌟第四步：计算顺序
从小到大。
🌟十四、课堂挑战
🎯挑战1
输入：
8 2 3 7 2
答案是多少？
请自己画表！
🎯挑战2
如果：
不能拿距离小于2的房子。
也就是说：
拿了 i，
那么：
-
i-1
-
i-2
都不能拿。
怎么办？
🎯挑战3
修改程序：
输出整个dp数组。
🎯挑战4（进阶）
如果房子是：
🌟一圈！
第1间和最后1间也算相邻！
该怎么办？
🌟十五、本课总结
✅1、今天学习了：
🌟“选”与“不选”DP
✅2、dp[i]表示：
前 i 间房子的最优答案
✅3、状态转移核心：
拿 or 不拿
✅4、动态规划重点：
🌟分析最后一步！
✅5、很多最优化问题都能这样做！
🌟十六、下节课预告
下一节课：
⚔️《最长上升火车——LIS启蒙》⚔️
这次：
我们要学习：
🌟最长上升子序列！
我们学习的动态规划内容终于要进入：
