缅甸做网站,热门视频素材,wordpress被屏蔽了api,wordpress用户中心在目录 引入简单实现稍加变形举一反三实战演练总结 引入 楼梯有个台阶#xff0c;每次可以一步上1阶或2阶。一共有多少种不同的上楼方法#xff1f; 怎么去思考#xff1f; 假设就只有1个台阶#xff0c;走法只有#xff1a;1 只有2台阶#xff1a; 11#xff0c;2 只有3台… 目录 引入简单实现稍加变形举一反三实战演练总结 引入 楼梯有个台阶每次可以一步上1阶或2阶。一共有多少种不同的上楼方法 怎么去思考 假设就只有1个台阶走法只有1 只有2台阶 112 只有3台阶 12 111 21 只有4台阶 112 22 121 1111211 不难观察到 3台阶的走法可以表示为1台阶的走法再22台阶的走法1 4台阶的走法可以表示为2台阶的走法再23台阶的走法1 自然递推出 n台阶的走法可以表示为n-2台阶的走法再2n-1台阶的走法1
解决步骤 1.定义状态 设dp[n]表示到达第n级台阶的不同方法总数。 2.状态转移方程 因为每次只能走1步或2步所以到达第n级台阶的方法数等于到达第(n-1)级台阶的方法数加上到达第(n-2)级台阶的方法数。 即dp[n]dp[n-1]dp[n-2]。 3.初始化 当n0时没有台阶认为有一种方法什么都不做因此dp[0]1。 当n1时只有一种方法即直接走上第一级台阶所以dp[1]1。 4.计算顺序从低到高依次计算每一级台阶的方法数直到n。 简单实现 跳台阶 https://www.acwing.com/problem/content/823/
一个楼梯共有 n n n 级台阶每次可以走一级或者两级问从第 0 0 0 级台阶走到第 n n n 级台阶一共有多少种方案。
输入格式
共一行包含一个整数 n n n。
输出格式
共一行包含一个整数表示方案数。
数据范围 1 ≤ N ≤ 15 1\leq N\leq15 1≤N≤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/?page1first_category_id1problem_id3367 思路 用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 N N 级台阶你一开始在底部每次可以向上迈 1 ∼ K 1\sim K 1∼K 级台阶问到达第 N N N 级台阶有多少种不同方式。
输入格式
两个正整数 N , K N,K N,K。
输出格式
一个正整数 a n s ( m o d 100003 ) ans\pmod{100003} ans(mod100003)为到达第 N N N 级台阶的不同方式数。
样例输入
5 2样例输出
8提示
对于 20 % 20\% 20% 的数据 1 ≤ N ≤ 10 1\leq N\leq10 1≤N≤10 1 ≤ K ≤ 3 1\leq K\leq3 1≤K≤3对于 40 % 40\% 40% 的数据 1 ≤ N ≤ 1000 1\leq N\leq1000 1≤N≤1000对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 100000 1\leq N\leq100000 1≤N≤100000 1 ≤ K ≤ 100 1\leq K\leq100 1≤K≤100。
思路分析 结合上面所学不难得出 dp[ i i i] dp[ i i i - 1] dp[ i i i - 2] ······ dp[ i i i - k k k] 当然这是 i ≥ k i\geq k i≥k的情况 对于 i k i k ik: dp[ i i i] dp[ i i i - 1] dp[ i i i - 2] ······ dp[0] 题解code
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
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/?page1first_category_id1problem_id3423 思路分析 只有一个空位那么只有 {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} {00,0,1} {1,0,0,1} 得到递推公式 写出状态转移方程 dp[ i i i] dp[ i i i-1]后面直接放0 dp[ i i i- k k 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]) % modelse:dp[i] (1 dp[i - 1]) % mod
print(dp[n])总结 线性动态规划Linear Dynamic Programming, 简称线性DP是一种动态规划的类型它主要处理具有线性结构的问题。 在这种问题中通常会有一个或多个序列作为输入而解决这些问题的目标是找到满足某些条件的最优解。 线性DP问题的特点是可以将问题分解为若干个子问题每个子问题仅涉及原问题的一个连续子序列并且这些子问题之间存在重叠和递推关系。 本篇博客从台阶问题入手逐步复杂化帮助更好地理解一维线性DP END 如果有更多问题或需要进一步的帮助可以在评论区留言讨论哦 如果喜欢的话请给博主点个关注 谢谢
