代码随想录算法第三十二天| LeetCode509斐波那契数、LeetCode70爬楼梯、LeetCode746使用最小花费爬楼梯

LeetCode 509 斐波那契数

题目链接：509.斐波那契数

文档讲解：理论基础 | 代码随想录

视频讲解：斐波那契数

思路与感想：题目确实挺简单的，由于第一次接触动态规划，虽然看了理论基础那篇，不过卡哥在视频和文档中讲的也偏通用解题步骤更像是一种框架性概述，对于完全没接触过动态规划的我，完全不知道怎么用动态规划写，所以就直接试着模拟这个过程写出来了。整体过程确实也简单，除却边界处理，只需要两个指针记录两个状态，然后在for循环不断更新这个状态就行了。后面看卡哥说的动态规划解法，讲的非常清晰把这道题目，而且也是按照理论基础里面的步骤，从定义dp数组，确定推导公式，dp数组初始化，遍历顺序，真的一步步讲的非常清楚。我觉得卡哥讲的一句话非常好，那就是用简单题熟悉贯彻方法论，再把这个方法论贯彻到更难的题目上。确实，回想跟着卡哥写队列和栈，二叉树，回溯题型的时候不也是这么一步步过来的吗！当然还有一种递归的方法，代码非常简短，可以把流程画成一棵二叉树来理解，叶子节点就是F(0)和F(1)。

收获：1.搞清了什么是递推公式和dp数组以及初始化

// 模拟法 class Solution { public int fib(int n) { int pre = 0; // 记录前前个数字 int cur = 1; // 记录前一个数字 if (n == 0 || n == 1) { // 如果n为0或者1直接返回n即可 return n; } int temp; // 临时变量用于存储前一个数字的值，方便传给pre for (int i = 2; i < n; i++) { temp = cur; // 存储 cur = pre + cur; // 更新cur pre = temp; // 原cur值传给pre } return pre + cur; } }

// 递归法 class Solution { public int fib(int n) { if (n == 0 || n == 1) { // 边界情况处理 return n; } return fib(n - 1) + fib(n - 2); // 每次求的fib都取决于前两个，递归可以看作一棵二叉树，一直深入到F(0) + F(1) } }

// 动态规划 class Solution { public int fib(int n) { if (n == 0 || n == 1) { // 边界情况处理 return n; } int[] db = new int[n + 1]; // 定义db数组，下标含义为db数组中第i个数就是斐波那契数列第i个数 db[0] = 0; // db数组的初始化，第零个数 db[1] = 1; // 第一个数 for (int i = 2; i <= n; i++) { db[i] = db[i - 1] + db[i - 2]; // 斐波那契数列的推导公式，db[i]状态只由前面两个数字决定 } return db[n]; // 返回db[n] } }

LeetCode 70 爬楼梯

题目链接：70.爬楼梯

文档讲解：代码随想录

视频讲解：爬楼梯

思路与感想：做完第一题感觉已经对动态规划的思路和模板有足够了解了，便尝试用动态规划思路做这道题，可惜我想半天也想不出来这个dp数组怎么定义，更别提这个i下标的含义了。后面看卡哥分析顿感十分巧妙，才知道为啥说这道题其实跟斐波那契数很像。关键思路就是如果你想要到爬到第i阶，那实际上你只能从i-1或者i-2阶登上去两种情况，但我当时想不通如果从i-2阶爬到i-1阶难道不是有1+1和2两种爬法吗，一共应该是三种才对啊，但事后一想这个分析里面应该有个不变量，那就是只能爬一次，如果说i-2阶用1+1爬法，那其实又回到了从i-1阶爬一阶到第i阶的情况了。这么一分析其实dp数组就出来了。既然爬到第i阶的方法数是由爬到第i-1和i-2阶的方法数决定的，那么dp[i]就意为爬到第i阶有几种方法，仔细一看这不就是题目要求的东西吗，也算是总结了一下，以后搭配着题目要求的东西去想dp数组的含义。递推公式也出来了dp[i] = dp[i - 1] + dp[i - 2]，初始化的话其实也是初始化dp数组最开始的几个，因为dp[i]是由前两个决定的，遍历顺序也就是从前往后，初始化dp[1]=1和dp[2]=2，这里不能说是像斐波那契数列初始化dp[0]=0或者1什么的，因为题目说了n是正整数，dp[0]本身就没啥意义，直接初始化dp[1]和dp[2]还更容易理解。

收获：1.根据题目要求找dp数组含义；2.善于根据案例分析找到递推关系

// 动态规划 class Solution { public int climbStairs(int n) { if (n == 1 || n == 2) { return n; // 处理边界情况 } int[] dp = new int[n + 1]; // 定义dp数组，下标含义是到第i阶楼梯有几种方法 dp[1] = 1; // 初始化dp数组 dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; // 这个规律在于第i阶楼梯上，而要想到第i阶楼梯上只有两种方法，第一种是i-1阶爬一阶，第二种是i-2阶爬两阶，这里即便你说i-2阶爬1+1到第i阶，那事实上又变成从i-1阶爬一阶的情况。这里只讨论爬一次的情况。也就是爬到第i阶的方法数，这个状态是由爬到i-1和i-2阶的方法数决定的。 } return dp[n]; } }

LeetCode 746 使用最小花费爬楼梯

题目链接：746.使用最小花费爬楼梯

文档讲解：代码随想录

视频讲解：使用最小花费爬楼梯

思路与感想：有了前两题的经验这道题写起来就轻松多了，dp数组很快就想到了含义，就是用的上道题总结的方法，那就是看题目要求什么，根据这个去想dp数组含义看看能不能行的通。推理出来是可以的，由于还是爬一次只能爬一阶或者两阶，所以就想到了斐波那契数列，这种递推公式，第i阶由前两阶决定，但是不同于之前的简单相加的，这里其实是更为孤立的存在，加上要求最小花费，我也很自然的想到了取i-1和i-2阶处花费的最小值，只是一开始没理解透彻题意，导致忘记加cost了，后面补上了，另外就是dp数组的初始化，由于跟前面的修改对应，所以都初始化0了，也就是说最开始选择起点的时候我是没有花费的，即相应dp值为0，只有往上跳的时候要加上相应的cost，这样一来就形成逻辑闭环了，遍历顺序由于跟前两题相似，所以也很容易确定了是从前往后遍历。

收获：1.第一次靠自己手撕动态规划，算是有点感觉了。

// 动态规划 class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length + 1]; // dp数组的含义是爬到第i阶需要的花费 dp[0] = 0; dp[1] = 0; for (int i = 2; i <= cost.length; i++) { dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]); // 由i - 1阶和i - 2阶决定第i阶花费，无论从哪个，都是d[i - 1]加上从该阶跳上去的花费即cost[i - 1]，由于求最小花费，所以i - 1和i - 2两种情况取最小值 } return dp[cost.length]; } }

今天刚接触动态规划，在很早之前我就听说了动态规划的鼎鼎大名了，今天算是撕开神秘面纱的一角了啊哈哈哈，当初还是把这个东西太神化了。有时候刷抖音看到一些算法大佬讨论这些的时候感觉都好牛逼，动不动飙几句英文什么dp，ac，oj，wa啥的，完全不解其意。现在也算是大致了解了。今天也开始复习之前的算法题了，下周给同学讲数据结构打算明天做一下ppt，分享一下这一个多月刷题的自我总结，还有各个题型的解题模板啥的，希望能讲的顺利。