【算法】动态规划专题① —

引入

楼梯有个台阶，每次可以一步上1阶或2阶。一共有多少种不同的上楼方法？

怎么去思考？
假设就只有1个台阶，走法只有：1
只有2台阶： 1+1，2
只有3台阶： 1+2， 1+1+1 ，2+1
只有4台阶： 1+1+2 ，2+2 ， 1+2+1 ，1+1+1+1，2+1+1
不难观察到
3台阶的走法可以表示为1台阶的走法再+2，2台阶的走法+1
4台阶的走法可以表示为2台阶的走法再+2，3台阶的走法+1
自然递推出：
n台阶的走法可以表示为n-2台阶的走法再+2，n-1台阶的走法+1

解决步骤：
1.定义状态：
设dp[n]表示到达第n级台阶的不同方法总数。
2.状态转移方程：
因为每次只能走1步或2步，所以到达第n级台阶的方法数等于到达第(n-1)级台阶的方法数加上到达第(n-2)级台阶的方法数。
即dp[n]=dp[n-1]+dp[n-2]。
3.初始化：
当n=0时，没有台阶，认为有一种方法（什么都不做），因此dp[0]=1。
当n=1时，只有一种方法，即直接走上第一级台阶，所以dp[1]=1。
4.计算顺序：从低到高依次计算每一级台阶的方法数直到n。

简单实现

跳台阶 https://www.acwing.com/problem/content/823/

一个楼梯共有 $n$ 级台阶，每次可以走一级或者两级，问从第 $0$ 级台阶走到第 $n$ 级台阶一共有多少种方案。

输入格式

共一行，包含一个整数 $n$ 。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

$1\leq N\leq15$

输入样例：

输出样例：

代码如下（示例）：

python">n = int(input())
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])

稍加变形

~~哎，就是玩给你几个楼梯弄坏~~

破损的楼梯 https://www.lanqiao.cn/problems/3367/learning/?page=1&first_category_id=1&problem_id=3367

在这里插入图片描述

思路：

用vis数组标记不能走的台阶即可

题解code：

python">mod = 1000000007
n, m = map(int, input().split())
a = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[0] = 1
vis = [0] * (n + 1)
for i in a:vis[i] = 1
for i in range(1, n + 1):if vis[i] == 0:dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[n])

举一反三

每次可以走一级或者两级或者三级，一共有多少种方案呢？
测试链接 https://www.acwing.com/problem/content/3646/

每次可以向上迈 1∼K 级台阶，答案又是多少呢？
在这里我们给出1-k级台阶的解法

台阶问题 https://www.luogu.com.cn/problem/P1192

题目描述

有 $N$ 级台阶，你一开始在底部，每次可以向上迈 $1\sim K$ 级台阶，问到达第 $N$ 级台阶有多少种不同方式。

输入格式

两个正整数 $N, K$ 。

输出格式

一个正整数 $ans\pmod{100003}$ ，为到达第 $N$ 级台阶的不同方式数。

样例输入

5 2

样例输出

提示

对于 $20\%$ 的数据， $1\leq N\leq10$ ， $1\leq K\leq3$ ；
对于 $40\%$ 的数据， $1\leq N\leq1000$ ；
对于 $100\%$ 的数据， $1\leq N\leq100000$ ， $1\leq K\leq100$ 。

思路分析：

结合上面所学，不难得出：
dp[ $i$ ] = dp[ $i$ - 1] + dp[ $i$ - 2] + ······ +dp[ $i$ - $k$ ]
当然，这是 $i\geq k$ 的情况
对于 $i < k$ :
dp[ $i$ ] = dp[ $i$ - 1] + dp[ $i$ - 2] + ······ +dp[0]

题解code

python">mod = 100003n, k = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):res = 0for j in range(min(i, k) + 1):res += dp[i - j]dp[i] = res % mod
print(dp[n])

结合前缀和能更快得出答案
什么？还不会前缀和？点此跳转 超细致讲解

code：

python">mod = 100003
n, k = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
pre_sum = [0] * (n + 2)
pre_sum[1] = 1
for i in range(1, n + 1):if i <= k:dp[i] = pre_sum[i] % modelse:dp[i] = (pre_sum[i] - pre_sum[i - k]) % modpre_sum[i + 1] = (pre_sum[i] + dp[i]) % mod
print(dp[n])

实战演练

安全序列 https://www.lanqiao.cn/problems/3423/learning/?page=1&first_category_id=1&problem_id=3423

在这里插入图片描述

思路分析：

只有一个空位，那么只有 {0}，{1}两种放法
两个空位，那么在上面的基础上放0或者隔k个0放1
{0,0}，{1,0}，{0,1}
三个空位，直接放0，或者隔k个0放1
{0,0,0} ，{1,0,0}，{0,1,0}， {0,0,1}
四个空位，继续递推
{0,0,0,0} {1,0,0,0} {0,1,0,0} {0,0,1,0} {0，0,0,1} {1,0,0,1}
得到递推公式：
写出状态转移方程：
dp[ $i$ ] = dp[ $i$ -1]（后面直接放0）+ dp[ $i$ - $k$ -1]（隔k个0后放1）

题解code：

python">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:dp[i] = (dp[i - k - 1] + dp[i - 1]) % modelse:dp[i] = (1 + dp[i - 1]) % mod
print(dp[n])

总结

线性动态规划（Linear Dynamic Programming, 简称线性DP）是一种动态规划的类型，它主要处理具有线性结构的问题。
在这种问题中，通常会有一个或多个序列作为输入，而解决这些问题的目标是找到满足某些条件的最优解。
线性DP问题的特点是可以将问题分解为若干个子问题，每个子问题仅涉及原问题的一个连续子序列，并且这些子问题之间存在重叠和递推关系。