70. 爬楼梯完全背包版本

From
卡码网
Status
回头复习下
Date
Apr 3, 2024
Tags
动态规划
完全背包
排列
Difficulty
简单
Link
https://kamacoder.com/problempage.php?pid=1067

题面

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

输入描述

输入共一行，包含两个正整数，分别表示n, m

输出描述

输出一个整数，表示爬到楼顶的方法数。

输入示例

3 2

输出示例

3

提示信息

数据范围：
1 <= m < n <= 32;
当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
  1. 1 阶 + 1 阶 + 1 阶段
  1. 1 阶 + 2 阶
  1. 2 阶 + 1 阶
 

思路

既然递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。
下标非0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的，dp[i]本身为0这样才不会影响结果
 

题解

 
Loading...