【算法】动态规划专题① ——线性DP python

引入

楼梯有个台阶，每次可以一步上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\le N\le 15$

输入样例：

5

输出样例：

8

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：

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(\mathrm{mod}100003)$，为到达第 $N$ 级台阶的不同方式数。

样例输入

5 2

样例输出

8

提示

• 对于 $20\%$ 的数据，$1\le N\le 10$，$1\le K\le 3$；
• 对于 $40\%$ 的数据，$1\le N\le 1000$；
• 对于 $100\%$ 的数据，$1\le N\le 100000$，$1\le K\le 100$。

思路分析：

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

题解code

mod = 100003

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

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

code：

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] % mod
    else:
        dp[i] = (pre_sum[i] - pre_sum[i - k]) % mod
    pre_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：

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

总结

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

本篇博客从台阶问题入手，逐步复杂化，帮助更好地理解一维线性DP

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢