代码随想录算法第三十二天| 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阶难道不是有11和2两种爬法吗一共应该是三种才对啊但事后一想这个分析里面应该有个不变量那就是只能爬一次如果说i-2阶用11爬法那其实又回到了从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阶爬11到第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]; } }今天刚接触动态规划在很早之前我就听说了动态规划的鼎鼎大名了今天算是撕开神秘面纱的一角了啊哈哈哈当初还是把这个东西太神化了。有时候刷抖音看到一些算法大佬讨论这些的时候感觉都好牛逼动不动飙几句英文什么dpacojwa啥的完全不解其意。现在也算是大致了解了。今天也开始复习之前的算法题了下周给同学讲数据结构打算明天做一下ppt分享一下这一个多月刷题的自我总结还有各个题型的解题模板啥的希望能讲的顺利。