代码随想录算法训练营第三十八天|509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯 

随想录文字讲解：代码随想录 (programmercarl.com)

随想录视频讲解：动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯_哔哩哔哩_bilibili

状态：做出来了

在写题之前，先看了左神的关于一维动态规划的一些视频。视频中对于一维动态规划的学习可以分为这样的渐进：

先是使用递归暴力的写出来。

然后因为递归中有很多重复计算，就写一个表来存储已经被计算过的数值，这样递归的第一条o(n)深度的从底顶就已经把基本后续需要的值给存到表里了。

这是从底到顶的记忆化动态规划。

底部的数据依赖其前部，所以有从顶到底的动态规划，也就是随想录的分析做法。

三种代码如下：

这个会超时（无记忆）

class Solution {
public:
    int digui(vector<int>& cost,int i)
    {
        if(i<=1) return 0;
        return min(digui(cost,i-1)+cost[i-1],digui(cost,i-2)+cost[i-2]);
    }
    int minCostClimbingStairs(vector<int>& cost)
    {
        int n=cost.size();
        return digui(cost,n);
    }
};

记忆化：

class Solution {
public:
    int digui(vector<int>& cost,int* arr,int i)
    {
        if(i<=1) return 0;
        if(arr[i]!=-1)
        return arr[i];
        int res=min(digui(cost,arr,i-1)+cost[i-1],digui(cost,arr,i-2)+cost[i-2]);
        arr[i]=res;
        return res;
    }
    int minCostClimbingStairs(vector<int>& cost)
    {
        int n=cost.size();
        int arr[n+1];
        memset(arr,-1,sizeof(arr));
        return digui(cost,arr,n);
    }
};

从顶到底

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        int n=cost.size();
        int dp[n+1];
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<=n;i++)
        dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        return dp[n];
    }
};

空间上还可以再优化，让dp数组只有两个长度。