DP爬台阶问题

1. 初级爬台阶 – 求最短步数

LC – 70

一次可以迈1-2个台阶，因此最短步数与前两个台阶有关。

Initial state: 第一阶：1步 ； 第二阶：1步

deduction function: f[n] = f[n – 1] + f[n – 2];

====可以推出，第三阶可以从第一阶迈出，可以从第二阶迈出，因此有两种可能。基本就是斐波那契数列求和。

public int climbStairs(int n) {
        if(n == 0) return 1;
        if(n == 1) return 1;        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;        for(int i = 0 ; i < n - 2 ; i++){
            dp[i + 2] = dp[i] + dp[i + 1];
        }        return dp[n - 1];
    }

2. 求最短开销

LC – 746

每个台阶的cost不同，还是只能迈1-2个台阶，这回求到顶点的最小开销。

Initial state: 2个台阶以内最小开销为cost[0], cost[1]中的最小值。0->1->dist or 0->2->dist

deduction function: f[n] = Math.min(dp[n – 1], dp[n – 2]) + cost[n]

====> 因为可以从n-1阶跳，也可以从n-2阶跳，选开销最小的台阶。

====>注意：可以从n->dist，n-1->dist，两个点都是有效的，因此结果选两个点中最小的。

public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        if(len == 0) return cost[0];
        if(len == 1) return Math.min(cost[0], cost[1]);        int[] dp = new int[len];        dp[0] = cost[0];
        dp[1] = cost[1];        for(int i = 2 ; i < len ; i++){
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }        return Math.min(dp[len - 1], dp[len - 2]);
    }

3. 1的进阶版

步数是2的幂。求有多少种组合。

因此：f[n] = f[n – 1] + f[n – 2] + f[n – 4] + … + f[1]

public static int countSteps(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;        for(int i = 0 ; i < n ; i++) {
            if(i == 0 || i == 1) dp[i + 1] = i + 1;
            else {
                int j = 0, tmp = 0;
                while(Math.pow(2, j) <= i + 1) {
                    tmp += dp[(int) (i + 1 - Math.pow(2, j))];
                    j++;
                }
                dp[i + 1] = tmp;
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }

莽就对了。。。