[数据结构与算法]LeetCode动态规划简答题合集

一、爬楼梯(70)

1.确定dp[i]的含义： 爬到第i层楼梯，有dp[i]种方法。

2.确定递推公式：dp[i-1]向上一个台阶就是dp[i]，dp[i-2]向上两个台阶也是dp[i]，所以dp[i]=dp[i-1]+dp[i-2]。

3.dp数组的初始化：dp[1] = 1，dp[2] = 2

4.确定遍历顺序：从dp[i]=dp[i-1]+dp[i-2]可以看出，一定是从前往后遍历。

5.举例推导dp数组：当n=4时，结果应为5。

??????????????dp[3]=dp[1]+dp[2]=3;

??????????????dp[4]=dp[2]+dp[3]=5;

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

二、使用最小花费爬楼梯(746)

1.确定dp[i]的含义：(i>2)?爬到第(i-2)层楼梯，最少的花费为dp[i]。

2.确定递推公式：Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

3.dp数组的初始化：dp[0] = 0，dp[1] = 0

4.确定遍历顺序：从Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])可以看出，一定是从前往后遍历。

5.举例推导dp数组：cost为[10,15,20]时，dp[2]=min(10,15)=10,dp(3)=min(15,30)=15，返回的是dp【3】=15。

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