目录
一、动态规划
二、动态规划分析步骤
三、例题分析
例题 P3367 破损的楼梯
P3423 安全序列
四、二维DP简介
五、例题分析
P1536 数字三角形
P389 摆花
一、动态规划
动态规划是一种算法思想，用于解决具有重叠子问题、最优子结构特征的问题。
- 重叠子问题：子问题是原问题的小版本
- 最优子结构：大问题的最优解包含小问题的最优解，通过小问题可以推导出大问题
楼梯有n个台阶，每次可以一步上1阶或2阶。一共有多少种不同的上楼方法？
- 原问题：n个台阶的上楼方案数
- 子问题：n - 1个台阶的上楼方案数、n - 2个台阶的上楼方案数、n - 3个台阶的上楼方案数……
最优子结构：子问题的最优解能否推出原问题的最优解？
- 要走到第n级台阶，要么从n - 1一步走过去，要么从n - 2一步走过去，因此：
- n个台阶的上楼方案数=n - 1个台阶的上楼方案数+n - 2个台阶的上楼方案数
无后效性：“未来与过去无关”，只需要考虑当下如何走到第n级，不需要考虑先前如何走到第n - 1、第n - 2，直接利用结果计算即可，最优子结构满足无后效性。
- 楼梯有n个台阶，每次可以一步上1阶、2阶、4阶。一共有多少种不同的上楼方法？
- 楼梯有n个台阶，每次可以一步上1阶、k阶。一共有多少种不同的上楼方法？
- 楼梯有n个台阶，每次可以一步上1阶、2阶、……、k阶。一共有多少种不同的上楼方法？
二、动态规划分析步骤
- 拆分子问题：将原问题拆解为子问题，找到问题之间的联系。
- 确定状态：此处的“状态”代指不同的问题，例如前面dp[x]表示上x台阶的方案数，其中x就是状态；确定状态就是确定问题需要几个维度的已知变量。一般是“前n个xxx为m的最大价值/最小价值/方案数”等。
- 状态转移方程：状态（子问题）之间是如何转移，即一个状态由哪几个状态转移来，或者该状态可以转移到哪些状态上。
- 实现：按照循环、记忆化搜索等方式求解最终状态（答案）。
n=int(input())
dp=[0]*(n+1)
dp[1]=1
dp[2]=2
for i in range(3,n+1):dp[i]=dp[i-1]+dp[i-2]
print(dp[n])
三、例题分析
例题 P3367 破损的楼梯
小蓝来到了一座高耸的楼梯前，楼梯共有 N 级台阶，从第 0 级台阶出发。小蓝每次可以迈上 1 级或 2 级台阶。但是，楼梯上的第 a1 级、第 a2 级、第 a3 级，以此类推，共 M 级台阶的台阶面已经坏了，不能踩上去。
现在，小蓝想要到达楼梯的顶端，也就是第 N 级台阶，但他不能踩到坏了的台阶上。请问他有多少种不踩坏了的台阶到达顶端的方案数？
由于方案数很大，请输出其对 10^9+7 取模的结果。
输入格式
第一行包含两个正整数 N（1≤N≤10^5）和 M（0≤M≤N），表示楼梯的总级数和坏了的台阶数。
接下来一行，包含 M 个正整数 a1,a2,…,aM（1≤a1<a2<a3<aM≤N），表示坏掉的台阶的编号。
输出格式
输出一个整数，表示小蓝到达楼梯顶端的方案数，对 10^9+7 取模。
在计算台阶方案时，如果当前台阶为坏的，则需要跳过该台阶的状态更新
vis[x]=1 表示第 x 级台阶损坏
n,m=map(int,input().split())
a=list(map(int,input().split()))dp=[0]*(n+1)
vis=[0]*(n+1)for x in a:vis[x]=1dp[0]=1
dp[1]=1-vis[1]for i in range(2,n+1):if vis[i]==1:continuedp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[n])
N = 100010
MOD = 1000000007n, m = map(int, input().split())
vis = [0] * N
f = [0] * N
X = list(map(int, input().split()))
for x in X:vis[x] = 1f[0] = 1
# 如果第1级台阶未破损（vis[1]为0），则方案数为1；如果破损（vis[1]为1），则方案数为0
f[1] = 1 - vis[1]
# 从第2级台阶开始计算到达每一级台阶的方案数
for i in range(2, n + 1):# 如果当前台阶是破损的，跳过该台阶，不计算到达该台阶的方案数if vis[i]:continue# 到达第i级台阶的方案数等于到达第i - 1级台阶和第i - 2级台阶的方案数之和，并对MOD取模f[i] = (f[i - 1] + f[i - 2]) % MODprint(f[n])
P3423 安全序列
小蓝是工厂里的安全工程师，他负责安放工厂里的危险品。
工厂是一条直线，直线上有 n 个空位，小蓝需要将若干个油桶放置在 n 个空位上，每 2 个油桶中间至少需要 k 个空位隔开，现在小蓝想知道有多少种放置油桶的方案，你可以编写一个程序帮助他吗？
由于这个结果很大，你的输出结果需要对 10^9+7 取模。
输入格式
第一行包含两个正整数 n，k，分别表示 n 个空位与 k 个隔开的空位。
输出格式
输出共 1 行，包含 1 个整数，表示放置的方案数对 10^9+7 取模。
样例输入
4 2样例输出
6说明
用 0 代表不放，1 代表放，6 种情况分别为：
0000，1000，0100，0010，0001，1001。
状态：dp[i]表示前 i 个位置的方案数 状态转移：dp[i]考虑两种情况：
- 不放置：从 dp[i - 1]转移
- 放置：从 dp[i - k - 1]转移
dp[i] = dp[i - 1] + (i - k - 1 >= 0)? dp[i - k - 1] : 1
MOD = 10**9 + 7
n, k = map(int, input().split())
dp = [1] + [0] * n
for i in range(1, n + 1):dp[i] = (dp[i - 1] + (dp[i - k - 1] if i - k - 1 >= 0 else 1)) % MOD
print(dp[n])MOD = 1000000007
n, k = map(int, input().split())
dp = [0] * (n + 1)# 初始状态：不放置也为一种方案
dp[0] = 1
for i in range(1, n + 1):if i - k - 1 >= 0:# 当第 i 个空位不放置油桶时，# 前 i 个空位的放置方案数就和前 i - 1 个空位的放置方案数是一样# 如果要在第 i 个空位放置油桶，那么它前面至少需要有 k 个空位是空闲的，# 前 i 个空位的放置方案数就和前 i - k - 1 个空位的放置方案数相关dp[i] = (dp[i - 1] + dp[i - k - 1]) % MODelse:# 空位数量太少，无法满足间隔 k 个空位放置油桶的要求dp[i] = (dp[i - 1] + 1) % MOD
print(dp[n])四、二维DP简介
- 二维DP和普通的DP本质都是一样的，只是状态的维度变成二维，即需要两个变量来定义子问题。
- 二维DP的更新可能会存在部分优化：前缀和、滚动数组（后续）
- 拆分子问题：将原问题拆解为子问题，找到问题之间的联系。
- 确定状态：此处的“状态”代指不同的问题，例如前面dp[x]表示上x台阶的方案数，其中x就是状态；确定状态就是确定问题需要几个维度的已知变量。一般是“前n个xxx为m的最大价值/最小价值/方案数”等。
- 状态转移方程：状态（子问题）之间是如何转移，即一个状态由哪几个状态转移来，或者该状态可以转移到哪些状态上。
- 实现：按照循环、记忆化搜索等方式求解最终状态（答案）。
五、例题分析
P1536 数字三角形
https://www.lanqiao.cn/problems/1536/learning/
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和（路径上的每一步只可沿左斜线向下或右斜线向下走）。
输入描述
输入的第一行包含一个整数 N (1≤N≤100)，表示三角形的行数。
下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 99 之间的整数。
输出描述
输出一个整数，表示答案。
状态1：<i, j>表示从(i, j)往下走的最大和
状态2：<i, j>表示到达(i, j)的最大和
n = int(input())
a = []
for i in range(n):a.append(list(map(int, input().split())))
dp = [[0] * n for i in range(n)]
# dp[i][j]表示从i,j出发的最大和
# 最终答案为dp[1][1]
# (i,j可以走到（i+1,j）或（i+1，j+1）
# dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j]# i需要从下往上更新, 枚举每一行
for i in range(n - 1, -1, -1):# 枚举第j列for j in range(i + 1):# 边界if i == n - 1:dp[i][j] = a[i][j]else:dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j]
print(dp[0][0])n = int(input())
a = []
for i in range(n):a.append(list(map(int, input().split())))
dp =[[0] * n for i in range(n)]
#dp[i][j]表示到达i,j的最大和#i需要从上往下更新, 枚举每一行
for i in range(n):#枚举第j列for j in range(i + 1):#边界if j == 0:dp[i][j] = dp[i - 1][j] + a[i][j]elif j == i:dp[i][j] = dp[i - 1][j - 1] + a[i][j]else:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j]
print(max(dp[n - 1]))
P389 摆花
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花，规定第 i 种花不能超过 ai 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入描述
第一行包含两个正整数 n 和 m，中间用一个空格隔开。
第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1、a2、......an。
其中，0<n≤100，0<m≤100，0≤ai≤100。
输出描述
输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 10^6+7 取模的结果。
- 给定 n 种花，数量不超过 ai，需要凑出 m 盆，求方案数。
- 状态 <i,j>：前 i 种花，数量为 j 盆的方案方案数；答案为 dp[n][m]
- 状态转移：dp[i][j] = dp[i - 1][j]+dp[i - 1][j - 1]+...+dp[i - 1][j - a[i]]
- 边界：dp[...][0]=1
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))#dp[i][j]表示前i种花, 选择出j盆的方案数
dp = [[0] * (m + 1) for i in range(n + 1)]
# 处理边界情况：当需要摆放的花的盆数为 0 时，不管有多少种花，都只有一种方案，即不摆花
for i in range(n + 1):dp[i][0] = 1for i in range(1, n + 1):for j in range(1, m + 1):#枚举第i种花选择的盆数为kfor k in range(min(a[i], j) + 1):
# 状态转移方程：前 i 种花摆 j 盆的方案数等于前 i - 1 种花摆 j - k 盆的方案数之和dp[i][j] += dp[i - 1][j - k]dp[i][j] %= 1000007
print(dp[n][m])