70.爬楼梯
力扣链接：70. 爬楼梯 - 力扣（Leetcode）
题目：
假设你正在爬楼梯。需要n阶你才能到达楼顶。
每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路：
假设要爬到三楼，每次可以爬一或两层，有两种选择，一种是从一楼爬两层楼梯到三楼，另一种是从二楼爬一层楼梯到三楼。即：3=2+1 or 3=1+2
同理，对于爬到二楼，也有两种情况，一种从一楼爬一层楼梯到二楼，另一种直接从0层爬两层楼梯到二楼。即：2=1+1 or 2=0+1(两种)
同理，爬到一楼，一种情况，从0层爬一层楼梯到一楼。即：1=0+1 (一种)
因此，对于爬到三楼，总共有三种情况。3=1+1+1 or 3=0+1+1 or 3=0+1+2
不难看出，爬到三楼的总方法数由爬到二楼，一楼总方法数之和组成。
假设dp[n]代表爬到第n层的总方法数，dp[n]=dp[n-1]+dp[n-2]
也就是动态规划的方法求解：其中dp[n]=dp[n-1]+dp[n-2]为状态转移方程
代码
public int climbStairs(int n) {// 设定dp[i]为爬到第i层楼梯的方法int[] dp = new int[n+1];/*状态方程：dp[i]=dp[i-1]+dp[i-2];解释：假设求爬到第三层楼梯的方法可以由第二层爬一楼到第三层，也可以由第一层爬两楼到第三层*//*dp[i]如何初始化dp[1]=1,dp[2]=2;至于dp[0]没有意义*/if(n <= 2) return n;dp[1] = 1;dp[2] = 2;for(int i = 3; i <= n; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
进阶
上题是每次只能移动一或两个台阶，倘若每次可以移动1,2,...,m个台阶，该如何求爬到n楼的总方法数
思路
假设 m=3 n=4 求爬到四楼的总方法数
和上面一样
爬到四楼可以由三楼爬一层楼梯，由二楼爬两层楼梯，由一楼爬三层楼梯。4=3+1 or 4=2+2 or 4=1+3
同理 爬到三楼 3=2+1 or 3=1+2 or 3=0+3 (四种)
同理 爬到二楼 2=1+1 or 2=0+1 (两种)
同理 爬到一楼 1=0+1 (一种)
因此，爬到四楼总共有七种方法
假设dp[i]为爬到第i楼的总方法，dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
代码
/*** 爬上n楼的总方法* @param m 每次可走台阶的最大值* @param n n楼* @return 返回爬上n楼的总方法*/public int climbStairs(int m,int n) {int[] dp = new int[n + 1];dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (i - j >= 0) dp[i] += dp[i - j];}}return dp[n];}
参考:代码随想录 ()
