【算法】动态规划专题① ——线性DP python-举一反三

每次可以走一级或者两级或者三级，一共有多少种方案呢？
测试链接 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])

---