代码随想录刷题笔记 DAY 37 | 动态规划理论基础 | 斐波那契数 No.509 | 爬楼梯 No.70 | 使用最小花费爬楼梯 No.746

文章目录

• • Day 37
  • • 00. 动态规划理论基础
    • 01. 斐波那契数（No. 509）
    • • 题目
      • 笔记
      • 代码
      • 02. 爬楼梯（No. 70）
      • • 题目
        • 笔记
        • 代码
        • 03. 使用最小花费爬楼梯（No. 746）
        • • 题目
          • 笔记
          • 代���

            Day 37

            00. 动态规划理论基础

            最常见的动态规划题目其实就是 求最值，比如说股票问题、背包问题，都是在求使用怎样的策略能使得整个系统达到一个最优化的状态。

            这是否和贪心比较类似呢？

            其实贪心算法和动态规划算法的区别还是比较大的，贪心算法每一次的最优解一定 包含 上一次的最优解，是局部的最优推出全局的最优，而动态规划的最优解不一定包含前一次的最优解，而是有可能是由更前面的部分推出的，所以通常通过 dp[] 数组来将前面的所有最优解来保存下来。

            动态规划其实是一个 穷举 的过程，得到最优解的前提就是要将所有的可能导致最优解的情况列出来，逐步推出最终的结果，而贪心更像是确定了一个路线，直接来走这个最优的路线，但这种最优通常是一种经验性的，较难推导的方式，相信做过贪心部分的朋友应该深有体会，这也就导致贪心得到的可能不是最优解，但相对的时间复杂度较低，而动态规划本质是穷举就会导致其时间复杂度相对较高。

            再来谈谈动态规划和暴力解法的区别，比如说斐波那契数列，使用递归来求会导致大量的重复计算，所以考虑引入备忘录，也就是记忆搜索的方法，记忆搜索的方法是自顶向下的，也就是要算 f(5) 要递归到 f(1) 才开始计算结果，而且由于递归的限制，思考其实可以采用自底向下的方式，从 f(1) 开始向上层递归，这其实就是动态规划的方法。

            01. 斐波那契数（No. 509）

            题目链接

            代码随想录题解

            题目

            斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

            F(0) = 0，F(1) = 1

            F(n) = F(n - 1) + F(n - 2)，其中 n > 1

            给定 n ，请计算 F(n) 。

            示例 1：

            输入：n = 2

            输出：1

            解释：F(2) = F(1) + F(0) = 1 + 0 = 1

            示例 2：

            输入：n = 3

            输出：2

            解释：F(3) = F(2) + F(1) = 1 + 1 = 2

            示例 3：

            输入：n = 4

            输出：3

            解释：F(4) = F(3) + F(2) = 2 + 1 = 3

            提示：

            • 0 public int fib(int n) { if (n == 0) return 0; if (n dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }} public int climbStairs(int n) { if (n