剑指Offer题目笔记26（动态规划的基础知识）

面试题88：

问题：

​ 一个数组cost的所有数字都是正数，它的第i个数字表示在一个楼梯的第i级台阶往上爬的成本，在支付了成本cost[i]之后可以从第i级台阶往上爬1级或2级。请计算爬上该楼梯的最少成本。

解决方案一：（递归：力扣超时）

解决方案：

​ 从第i级台阶往上爬的最少成本应该是从第i-1级台阶往上爬的最少成本和从第i-2级台阶往上爬的最少成本的较小值再加上爬第i级台阶的成本。故该关系的状态转移方程为dp（i） = min(dp(i-1),dp(i-2)) + cost[i]。

源代码：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        return Math.min(dfs(cost,len-1),dfs(cost,len-2));
    }

    private int dfs(int[] cost,int len){
        if(len < 2){
            return cost[len];        
        }
        return Math.min(dfs(cost,len-1),dfs(cost,len-2)) + cost[len];
    }
}

解决方案二：（使用缓存的递归）

解决方案：

​ 不使用缓存的话，需要反复计算前一个递归。例如求f（9）就需要先求f（8）和f（7），而计算f（8）就需要计算f（7）和f（6），以此类推，需要重复计算的数据量太大、时间复杂度很高。故为了避免重复计算带来的问题，一个常用的解决办法是将已经求解过的问题的结果保存下来。在每次求解一个问题之前，应先检查该问题的求解结果是否已经存在。如果问题的求解结果已经存在，则不再重复计算，只需要从缓存中读取之前求解的结果。

源代码：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len];
        dfs(cost,dp,len-1);
        //dfs(cost,dp,len-2);这条代码是我加上去的，不然跑不过样例：[1,100]，加了还是超时，力扣还差两个样例跑不过。
        dfs(cost,dp,len-2);
        return Math.min(dp[len-1],dp[len-2]);
    }

    private void dfs(int[] cost,int[] dp,int len){
        if(len < 2){
            dp[len] = cost[len];
        }else if(dp[len] == 0){
            dfs(cost,dp,len-1);
            dfs(cost,dp,len-2);
            dp[len] = Math.min(dp[len-1],dp[len-2]) + cost[len];
        }
    }
}

解决方案三：（空间复杂度为O（n）的迭代）：

解决方案：

​ 自下而上地解决这个过程，也就是从子问题入手，根据两个子问题f（i-1）和f（i-2）的解求出f（i）的结果。

源代码：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        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]);
    }
}

解决方案四：（空间复杂度为O（1）的迭代）：

解决方案：

​ 前面用一个长度为n的数组将所有f（i）的结果都保存下来。求解f（i）时只需要f（i-1）和f（i-2）的结果，从f（0）到f（i-3）的结果其实对求解f（i）并没有任何作用。也就是说，在求每个f（i）的时候，需要保存之前的f（i-1）和f（i-2）的结果，因此只要一个长度为2的数组即可。

源代码：

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

        return Math.min(dp[0],dp[1]);
    }
}