7. DP

背包问题Knapsack Problem

746. Min Cost Climbing Stairs

• 经典的0-1背包问题

• 4步走

• 1. dp[i] means min cost to reach i-th floor

     2.dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

     3.dp[0] = cost[0], dp[1] = cost[1]

     4.dp[n]-> min(dp[n - 1], dp[n - 2])

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