首页 > 代码库 > 动态规划--上楼梯
动态规划--上楼梯
题目：假设你需要进入一个房间，但是房间在楼上，你需要走完n阶台阶，才能到楼上，如果你一次性可以走1、2或3个台阶，可以计算出你一共有多少种方案去走完所有的台阶进入房间呢？
解题思路：定义一个状态函数f(n)用来表示如果要走n阶台阶一共可以有方案数量，则f(n)=f(n-1)+f(n-2)+f(n-3)。当n＝1时只有一中方案，当n＝2时有两种方案(1,1;2)，当n＝3时有4种方案(1,1,1;1,2;2,1;3)，依次类推。
具体算法(Java版)
1 /** 2 * 计算n个台阶一共有多少中走法 3 */ 4 public class Step { 5 6 public static int walk(int n, int[] stepWays) { 7 if (n <= 0) 8 return 0; 9 int count = 0;10 for (int i = 0; i < stepWays.length; i++) {11 if (n == stepWays[i]) {12 count += 1;13 } else {14 count += walk(n - stepWays[i], stepWays);15 }16 }17 return count;18 }19 20 public static void main(String[] args) {21 int[] stepWays = new int[] { 3, 1, 2};22 int n = 10;23 System.out.println(walk(n, stepWays));24 }25 26 }
如果有什么问题，可以一起交流！
动态规划--上楼梯
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。