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

509. 斐波那契数 - 力扣（LeetCode）

思路:

• 这里主要讲解动态规划做法的思路

• 1. 确定dp数组以及下标的含义

     • dp[i]的定义为：第i个数的斐波那契数值是dp[i]

  2. 确定递推公式

     • 状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

  3. dp数组如何初始化

     dp[0] = 0;
     dp[1] = 1;

  4. 确定遍历顺序

     • 从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]依赖dp[i - 1]和dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

我的AC代码

递归法

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

动态规划

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int fib(int n) {
        vector<int> dp(n + 2); // 为了防止数组溢出
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

动态规划(改良空间复杂度)

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int fib(int n) {
        if(n < 2) {
            return n;
        }
        vector<int> dp(2);
        int sum = 0;
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; ++i) {
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return sum;
    }
};

标准答案

动态规划

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        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];
    }
};

动态规划(改良空间复杂度)

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

递归

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

70. 爬楼梯 - 力扣（LeetCode）

思路:

使用动态规划(和509. 斐波那契数 - 力扣（LeetCode）这一题本质上是一样的)

1. 确定dp数组以及下标的含义

   • dp[i]的定义为：到达第i个楼梯的方法数是dp[i]

2. 确定递推公式

   • 状态转移方程 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];中可以看出，dp[i]依赖dp[i - 1]和dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

我的AC代码

动态规划

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 2);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

动态规划(优化空间复杂度)

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2) {
            return n;
        }
        vector<int> dp(3);
        dp[1] = 1;
        dp[2] = 2;
        int sum = 0;
        for(int i = 3; i <= n; ++i) {
            sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return sum;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

思路:

使用动态规划

1. 确定dp数组以及下标的含义

   • dp[i]的定义为：到达第i个楼梯花费的体力是dp[i]

2. 确定递推公式

   • 状态转移方程 dp[i] = min(dp[i - 1] + cost[i -1], dp[i - 2] + cost[i - 2]);

3. dp数组如何初始化

   dp[0] = 0;
   dp[1] = 0;

4. 确定遍历顺序

   • 从前往后

这道题要注意的是：因为题目说可以从0或者1开始，那么说明到达0或者1楼梯所花费的体力是免费的

我的AC代码

动态规划(没注意到题意该如何更好地理解才写得这么麻烦)

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp0(n + 1, 0);
        vector<int> dp1(n + 1, 0);
        dp0[1] = cost[0];
        for(int i = 1; i <= n; ++i) {
            if(i > 1) {
                dp0[i] = min(dp0[i - 1] + cost[i - 1], dp0[i - 2] + cost[i - 2]);
                dp1[i] = min(dp1[i - 1] + cost[i - 1], dp1[i - 2] + cost[i - 2]);
            }
            else {
                dp0[i] = dp0[i - 1] + cost[i - 1];
            }
        }
        return min(dp0[n], dp1[n]);
    }
};

动态规划(优化代码)

// 时间复杂度O(n),空间复杂度O(n)
// 可以选择从0或者1起跳则说明到0或者1都是免费的
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1, 0);
        dp[1] = dp[0] = 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];
    }
};

动态规划(优化空间复杂度)

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(2, 0);
        dp[1] = dp[0] = 0;
        for(int i = 2; i <= n; ++i) {
            int sum = min(dp[1] + cost[i -1], dp[0] + cost[i - 2]);
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

标准答案

动态规划

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1);
        dp[0] = 0; // 默认第一步都是不花费体力的
        dp[1] = 0;
        for (int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()];
    }
};

动态规划(优化空间复杂度)

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp0 = 0;
        int dp1 = 0;
        for (int i = 2; i <= cost.size(); i++) {
            int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
            dp0 = dp1; // 记录一下前两位
            dp1 = dpi;
        }
        return dp1;
    }
};