1. 斐波那契数 爬楼梯 使用最少花费爬楼梯

1. 斐波那契数

版本一：一维数组记录型

class Solution {
public:
    int fib(int n) {
        if(n <= 1)
            return n;
        std::vector<int > dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i<=n; ++i){
               dp[i] = dp[i-1] + dp[i-2]; 
        }
        return dp[n];
    }
};

利用一维数组进行记录。目的 明确动态规划的 的五步

• 确定dp数组的含义
• 确定递推公式
• 初始化问题
• 遍历问题
• 日志问题

版本二：两个变量记录

class Solution {
public:
    int fib(int n) {
        if(n <= 1)
            return n;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        int sum = 0;
        for(int i = 2 ;i <= n ; ++i){
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return sum;
    }
};

因为每一次都只用到前面两个的数据，因此可以简化数组。降低空间复杂度。

版本三：递归

class Solution {
public:
    int fib(int n) {
        if(n <= 1)
            return n;
        return fib(n-1) + fib(n-2);
    }
};

使用自顶向下的进行计算，中间存在重叠的子问题。可以利用一个数组进行记忆化搜索。

2. 爬楼梯

版本一：空间没有优化的版本

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2 ) return n;
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; ++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

确定五部曲，明确每一步含义。

版本二：优化空间

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2 ) return n;
        int dp[2];
        dp[0] = 1;
        dp[1] = 2;
        int sum = 0;
        for(int i = 3; i <= n; ++i){
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

因为每一次都只是用到前面两个dp的值，返回的也只是一个对应的dp值，所以可以进行空间的优化。

3. 使用最小花费爬楼梯

版本一：没有进行空间优化

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

        return min(dp[height-1] , dp[height - 2]);
    }
};

版本二： 空间优化

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

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