概述
思路
该题问的是有多少种方式。就是一个排列问题。
那么可以尝试用背包问题来解决。又因为可以重复的上台阶，所以是一个完全背包问题。
把解题的总个数target看作为背包的容量，每次迈的台阶数看做物品。这就变为一个完全背包问题求排列数的问题了。
用动态规划解决
1.定义dp数组的含义
dp[j]表示，当有j个台阶的时候有dp[j]种方式可以登上去。
2.递推公式
因为是排列问题，所以递推公式就是dp[j]+=dp[j-i];
注：理解不了就记住，在排列和组合问题中，递推公式一般都是它。
3.初始化
dp[0]=1;
根据dp数组的定义和递推公式可以知道dp[0]=1;
4.遍历顺序
根据递推公式可以知道应该顺序遍历。又因为是排列问题，所以要先遍历背包再顺序遍历物品。
5.打印dp数组
dp数组的最后一个元素就是结果
代码
public class Solution {
public int jumpFloorII(int target) {
int dp[] = new int[target+1];
dp[0]=1;
dp[1]=1;
for(int j = 2;j<=target;j++){
for(int i = 1;i<=target;i++){
if(j-i>=0)
dp[j]+=dp[j-i];
}
}
return dp[target];
}
}最后
以上就是舒适项链为你收集整理的JZ71 跳台阶扩展问题的全部内容，希望文章能够帮你解决JZ71 跳台阶扩展问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复