[数据结构与算法]70. 爬楼梯

题目:

假设你正在爬楼梯。需要?n?阶你才能到达楼顶。

每次你可以爬?1?或?2?个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：

１）思路１

将此题看作简单的动态规划问题

1.1)dp[i]:表示爬到第i层楼有多少种方案

1.2)初始化:

爬到第一层有1种

爬到第二层有2种

1.3)推导公式:

dp[i] = dp[i-1] + dp[i-2]

可以从以下角度思考:

如果此时在第i-1层,那再爬1层就到第i层了

如果此时在第i-2层,那再爬2层就到第i层了

所以爬到第i层楼的方案数等于爬到第i-1和i-2层楼的方案数之和

class Solution {
    public int climbStairs(int n) {
        if(n<=2) return n;

        int [] dp = new int [n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i<dp.length; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

２）思路２

将此题看作完全背包问题中的排列问题.

2.1)为什么可以看作是完全背包问题而不是0-1背包问题?

因为本题中的每一次可爬台阶数1或者2是可以无数次重复选择的,即跳了1阶，还可以继续跳1阶,同理2也是.

2.2)为什么可以看作是排列问题而不是组合问题?

前提:组合不看元素间的顺序,排列要看元素间的顺序.

因为如果n=3,那方案1:{1,2}?和方案2:{2,1}都是上三个台阶，但是这两种方法不一样！

class Solution {
    public int climbStairs(int n) {
        int dp[] = new int[n+1];
        dp[0]=1;
        
        int[] nums = new int [2];
        nums[0] = 1;
        nums[1] = 2;
        
        for(int i = 0;i<=n;i++){
            for(int j = 0 ; j<nums.length; j++ ){
                if(i>=nums[j])
                dp[i] +=dp[i-nums[j]];
            }
        }
        return dp[n];
    }
}