解法一：（动态规划）num[i]表示i有几种不同的方法可以爬到楼顶n
动态规划方程为：
n u m [ i ] = { 0 , i = n 1 , i = n − 1 , n − 2 ∑ i + 1 i + 3 n u m [ j ] , o t h e r s num[i]=\begin{array}{l} \left\{\begin{matrix} 0,i=n\\ 1,i=n-1,n-2\\ \sum_{i+1}^{i+3} num[j],others \end{matrix}\right. \end{array} num[i]=⎩ ⎨ ⎧0,i=n1,i=n−1,n−2∑i+1i+3num[j],others
import java.util.*;/*** @author longyy* @version 1.0*/
class Solution79 {public int climbStairs(int n) {if(n == 0) return 0;if(n == 1) return 1;int[] nums = new int[n+1];nums[n] = 0;nums[n-1] = 1;nums[n - 2] = 2;if(n > 2){for(int i = n-3; i >= 0; i--){for(int j = i+1; j-i < 3; j++){nums[i] += nums[j];}}}return nums[0];}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();Solution79 sol = new Solution79();System.out.println(sol.climbStairs(n));}
}
注意：
- 累加nums时，
j∈[i+1,i+3)保证只走1或2步 dp初始化为dp[n+1]，dp[i]表示i到n可以有多少种走法；初始状态为nums[n] = 0; nums[n-1] = 1; nums[n - 2] = 2;，返回值为dp[0]
