leetcode刷题

leetcode刷题经历

一、数组

简单题

1. 两数之和

• 暴力解法，时间复杂度O(n²)
• 哈希表，寻找差的时候O(1)，总时间复杂度O(n)

26. 删除有序数组中的重复项

• 快慢指针，快指针检测不同来更换慢指针。时间复杂度O(n)

27. 移除元素

• 快慢指针，快指针检测不同来更换慢指针。时间复杂度O(n)
• 双指针优化，一个从左边向右遍历，一个从右边向左遍历。时间复杂度O(n)，不过数组总共只遍历一次。
  • 小细节:为了防止更换过来相同的元素，可以让左指针指的元素不等于指定元素再移动(放在else语句中)

35. 搜索插入位置

• 二分法查找:时间复杂度：O(log_n)

69. x的平方根

• 二分法查找:时间复杂度O(log_n)

283. 移动零

• 双指针：用非零快指针交换零慢指针，时间复杂度O(log_n)

367. 有效的完全平方数

• 二分查找:时间复杂度O(log_n)

704. 二分查找

• 注意区间开闭

977. 有序数组的平方

• 暴力解法，先平方后排序

• 双指针法

  由于数组有序，数组平方后最大值只能在数组两端，那么可以定义一个同等大小数组，指向新数组最后一个元素，然后一个一个向里面填

中等题

54. 螺旋矩阵

• 将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，知道输出最内层的元素。
• 对于每层更新top,left,right,bottom
• 从左到右遍历上侧元素，依次为(top,left)到(top,right)
• 从上到下便利右侧元素，依次为(top+1,right)到(bottom,right)
• 如果left<right且top<bottom，则从右到左遍历下侧元素，依次为
• (bottom,right−1) 到(bottom,left+1)，以及从下到上遍历左侧元素，依次为(bottom,left)到(top+1,left)
• 遍历完当前层的元素之后，将left和top分别增加1，将right和bottom分别减少1，进入下一层继续遍历，直到遍历完所有元素为止。
• 时间复杂度为O(mn)

59. 螺旋矩阵 II

• 顺时针画矩阵，填充上行从左到右、填充右列从上到下、填充下行从右到左、填充左列从下到上
• 每一层填充，填充n/2层，每层更新startx，starty
• 统一左闭右开
• 时间复杂度O(n²)

209. 长度最小的子数组

• 暴力解法：时间复杂度O(n^{n^2})
• 滑动窗口：时间复杂度O(n)，动态调整滑动窗口的起始位置是精髓

904. 水果成篮

• 滑动窗口，是用哈希表unordered_map存储非重复数，当超过两个果篮时，从左边缩小滑动窗口，时间复杂度为O(log_n)

困难题

93. 最小覆盖字串(Haven’t done it yet)

二、链表

简单题

160. 相交链表

• 先求出两链表长度的插值，然后让curA移动到和curB对其的位置。然后二者一起动，判断指向节点是否相同。

203. 移除链表元素

206. 反转链表

• 注意存储节点
• 双指针法
• 递归法

中等题

19. 删除链表的倒数第N个节点

• 快慢指针，快指针提前移动N次，然后同时移动，删除慢指针指向的节点。

24. 两两交换链表中的节点

• 注意存储节点以及更换next的顺序

142. 环形列表II

• 一种直观思路是：遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以实现。时间、空间复杂度都为O(N).
• 快慢指针：让快指针每次移动两个位置，慢指针移动一个位置，若存在环，则两指针必定相遇。从起始位置设一个指针ptr，同时移动slow和ptr，两者会在环入口处相遇

707. 设计链表

困难题

三、哈希表

简单题

202. 快乐数

• 使用哈希表unordered_set来判断sum是否重复出现，如果重复了就是return false，否则一直找到sum为1为止。

242. 有效的字母异位词

• records记录字符串里字符出现的次数，再遍历目标字符串，每个字符都减一，最后若records中有元素不为0，则return false ,反之，return true

349. 两个数组的交集

• 要求去重且不要求有顺序，可以使用unordered_set，如果字符串二中的字符存在set中，则取出。

350. 两个数组的交集 II

• 哈希表：将属性多的数组存入map，记录每个元素出现的次数，遍历另一个数组，若map中出现则插入结果数组中，若有元素数量减为0，则记得在map中erase元素
• 排序和双指针：将两个数组排好序，两个指针分别遍历两个数组，数值小的移动，相同时则插入结果数组并同时移动。

383. 赎金信

• 和242. 有效的字母异位词思路相同

中等题

15. 三数之和

• 哈希法：两层循环确定a与b的数值，使用哈希发来确定0-(a+b)，先排序，如果第一个数大于零，则不可能凑成三元组。对a去重只用比较相邻两数，对b去重则需要对相邻三数，如果只判断相邻两数则会相同数指利用一次，如果更多则会造成重复。
• 双指针：先排序，遍历数组，定一个下表left在i+1上的位置，定义下表right在数组结尾的位置上，若三数之和大于0，说明三数之和大了，right向左移动，若三数之和小于0，left向右移动，直到left与right相遇，期间注意去重。

18. 四数之和

• 与三数之和相同思路，多一重循环。存在一些其他剪枝
  • 确定第一个数后，如果nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target，则无论剩下三个数取什么值，四个数和一定大于target，退出第一重循环
  • 确定第一个数后，如果nums[i]+nums[n-3]+nums[n-2]+nums[n-1]>target，则无论剩下三个数取什么值，四个数和一定大于target，第一重循环直接进入下一轮
  • 确定前两个数之后，如果nums[i]+nums[j]+nums[j+1]+nums[j+2]>target，则无论剩下两个数去什么值，和一定大于target，退出第二重循环
  • 确定前两个术后，如果nums[i]+nums[j]+nums[n-2]+nums[n-1]<target,则无论剩下两个数取什么值，四数之和一定小于target，二重循环进入下一轮。

49. 字母异位词分组

• 排序：互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定相同，因此将排序之后的字符串作为哈希表的键，值为字符串数组。

438. 找到字符串中所有字母异位词

• 滑动窗口，判断构成的两组vector是否相等，而不必去判断是否为零数组

454. 四数相加 II

• 首先定义一个unordered_map,key放a和b两数之和，value放a和b两数之和出现的次数，遍历AB两数组，统计两数组元素之和和出现的次数放到map中，定义int变量count同济四数之和为0出现的次数，遍历CD数组，如果0-(c+d)在map中出现过，则统计出到count.

困难题

四、字符串

简单题

344. 反转字符串

• 双指针

459. 重复的子字符串

• 暴力，外层循环从开始到字符串一半遍历作为子串结束位置，采用一重循环判断s[i]是否等于s[j-i]，字符串肯定是子串的整数倍。
• 若由重复的子字符串组成则两个字符串连起来其中必有原字符串，掐头去尾 return (s+s).find(s,1) != s.size()
• KMP

541. 反转字符串 II

• 反转i到i+k，每次增加2k，注意最后剩余小于k时反转全部。

剑指Offer 05. 替换空格

• 首先扩充数组到每个空格替换成“%20”之后的大小，然后从后向前替换空格，用双指针法，i指向旧长度的末尾，j指向新长度的末尾。

剑指Offer 58 - II. 左旋转字符串

• 使用整体反转+局部反转。先反转前n个字符，再反转剩下字符，再反转整个字符串。

中等题

28. 实现strStr()

• KMP算法，关键计算最大相等前后缀长度，构建next数组
  • 1. 初始化：两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置
    2. 处理前后缀不相同的情况：前缀向前回退j=next[j-1]
    3. 处理前后缀相同的情况：向后移动i和j，同时还要将j赋给next[i]。

151. 反转字符串中的单词

• 解题思路：

  • 移除多余空格

    使用双指针

  • 将整个字符串反转

    自己写反转函数，双指针

  • 将每个单词反转

    同上

困难题

五、栈与队列

简单题

20. 有效的括号

• 遍历字符串，如果是左括号就push对应的右括号，如果是右括号且和栈顶相等就pop，如果遍历完栈不为空或者遍历右括号的时候发现已经空了则为错，否则为对。

225. 用队列实现栈

• 初始化两个队列，其中一个是辅助队列。pop时将其他元素push进第辅助队列中，再pop剩下的那个元素。最后将辅助队列赋值给主队列，然后清空辅助队列。
• 或者只用一个队列，将元素push进辅助队列的操作可以改为push到队尾。

232. 用栈实现队列

• 一个输入栈，一个输出栈。pop时当输出栈为空时将输入栈pop到输出栈，再从输出栈pop

1047. 删除字符串中的所有相邻重复项

• 思路同20.有效的括号

中等题

150. 逆波兰表达式求值

• 和1047.删除字符串中的所有相邻重复项思路一样，只不过这里不需要做消除，而是做运算。

347. 前K个高频元素

• 首先使用unorderer_map统计元素出现频率，定义一个小顶堆，每次将元素push进去。当堆中元素超过k时pop（即小顶堆固定大小为K）。找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序输出到数组。

困难题

239. 滑动窗口最大值

• 我们自己实现一个单调队列，只维护有可能成为创就里最大值的元素，并保证队列里的元素数值由大到小。使用dequeue双向队列，封住一边。其实就是stack和queue默认的底层实现容器。
  • 定义方法pop(value):如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。
  • 定义方法push(value):如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，知道push元素的数值小于等于队列入口元素的数值为止。
• 先将前k元素放进队列，记录下前k元素的最大值，然后不断滑动窗口移除最前面的元素、加入最后面的元素，并记录对应的最大值。

六、二叉树

简单题

100. 相同的树

• 类似101，先剪枝，然后递归比较左子树的左节点与右子树的左节点，以及左子树的右节点以及右子树的右节点。

101. 对称二叉树

• 先剪枝，左右空不对称或值不对称都返回false。再递归比较左子树的左节点与右子树的右节点，以及左子树的右节点与右子树的左节点。

104. 二叉树的最大深度

• 深度搜索，
• 层序遍历，每一层计数器加1.
• 递归，1+左右子树深度的最大值。

110. 平衡二叉树

• 递归。获取左右子树的高度，如果左右子树高度之差大于1，返回false，否则返回true。

111. 二叉树的最小深度

• 深度搜索
• 层序遍历，叶子结点的话返回，不是的话继续遍历。

112. 路经总和

• 递归。回溯。确定递归返回类型及参数。确定终止条件。不好统计路径总和可以从targetSum向下减，直到叶子节点判断sum是否为0.

144. 二叉树的前序遍历

• 第一种解法：递归遍历，中左右
• 第二种解法：借助栈不递归，先压根节点，弹出后再压右节点，再压左节点。这样保证中间节点之后先左再右。
• 第三种解法：标记法，要处理的节点放入栈之后，紧接着放入一个空指针作为标记。

94. 二叉树的中序遍历

• 第一种解法：递归遍历，左中右
• 第二种解法：因为访问元素和要处理的元素顺序不一致，因此类似前序遍历的迭代方法不行。可以借助指针来访问节点。节点先找到最左侧节点，并将中间访问到的元素压栈。直到找到叶子节点后开始弹出中间节点，后接着迭代右节点。
• 第三种解法：标记法，要处理的节点放入栈之后，紧接着放入一个空指针作为标记。

145. 二叉树的后序遍历

• 第一种解法：递归遍历，左右中
• 第二种解法：与前序遍历差不多。先压根节点，弹出后再压左节点，再压右节点，之后对结果倒序，就得到左右中。
• 第三种解法：标记法，要处理的节点放入栈之后，紧接着放入一个空指针作为标记。

226. 反转二叉树

• 递归法，确定返回值，确定终止条件，确定单层递归的逻辑
• 深度遍历，
• 层序遍历，每个节点都反转两个字节点。

257. 二叉树的所有路径

• 递归。终止条件为叶子节点，对叶子节点进行处理，将路径变为string值传入result结果集中。单次调用首先把当前节点push进路径，然后找左子树路径，之后pop回当前节点，再找右子树路径，pop回当前节点，最后返回得到的结果集。

404. 左叶子之和

• 递归。终止条件为空节点和叶子节点；递归左叶子节点以及右叶子节点。
• 迭代。遍历的时候判断是不是左叶子。

501. 二叉搜索树中的众数

• 将整棵树遍历，用map统计概率。将map存储成vector，按照频率进行排序。然后取前面高频的元素存入result；
• 双指针，定义一个指针指向前面遍历的节点。每两两相同便将count加1，当count等于maxCount时直接存入结果数组；当count大于maxCount时更新maxCount，清空结果数组，并将当前节点推入结果数组。

530. 二叉搜索树的最小绝对差

• 中序遍历二叉搜索树，构造一个递增数组。求相邻元素之间最小绝对差。

572. 另一棵树的子树

• 第一种解法：层序遍历，每个节点都和子树比较是否相同。

589. N叉树的前序遍历

• 深度遍历，借助栈，每次取出后从后往前放子节点。

590. N叉树的后序遍历

• 深度遍历，借助栈，借助前序遍历然后反转结果。

617. 合并二叉树

• 迭代。使用队列模拟层序遍历。如果两个节点的左节点都不为空，都入队列；如果两个节点的右节点都不为空，都入队列；如果第一棵树左节点为空第二棵树左节点不为空，直接赋值；右节点同理。
• 递归。确定返回值和参数；确定终止条件，确定单层调用逻辑。

637. 二叉树的层平均值

• 第一种解法，层序遍历，每层求平均。
• 第二种解法，深度优先，记录每个level的个数以及总和，最后求平均。

669. 修剪二叉搜索树

• 递归。三部曲。单层递归逻辑：如果当前节点小于low，去找右子树；如果当前节点大于high，去找左子树。如果当前符合，就去让左右子树都符合，最后return当前节点。

700. 二叉搜索树中的搜索

• 递归。确定返回值以及参数；确定终止条件；确定单层调用逻辑。
• 迭代。如果节点数值大于val，向左找；反之，向右找。找到空值为止。

中等题

98. 验证二叉搜索树

• 中序遍历得到数组，比较数组是不是递增。
• 递归。中序遍历，取一个全局变量记录最大值，若在遍历途中发现有最大值大于后面节点，返回false。
• 递归。中序遍历，取一个全局节点用来记录前一个节点，若出现前一个节点比当前节点大，则返回false。

102. 二叉树的层序遍历

• 第一种解法：借用辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑。
• 第二种解法：递归法，并不是层序遍历，借助二级数组按索引存放。

105. 从前序与中序遍历序列构造二叉树

• 同106. 注意区间的左闭右开。

106. 从中序与后序遍历序列构造二叉树

• 递归。
  • 先确定递归结束条件。
  • 后序遍历数组最后一个元素，就是当前的中间节点。
  • 找中序遍历的切割点。
  • 切割中序数组，得到中序左数组和中序右数组。
  • 根据长度切割后序数组，得到后序左数组和后序右数组。
  • 递归，左节点传中序左，后序左。
  • 递归，右节点传中序右，后序右。

107. 二叉树的层序遍历II

• 与102解法相同，最后return前做一次reverse。

108. 将有序数组转换为二叉搜索树

• 递归。三部曲。递归终止条件，left>right。单层递归逻辑：找中间节点存入树节点，对树左子树用左边数组构造；对树右子树用右边数组构造。

116. 填充每个节点的下一个右侧节点指针

• 层序遍历，每一层使用cur存该层前一个遍历的节点，令其next指针指向当前节点。

117. 填充每个节点的下一个右侧节点指针

• 与116一样。116有待优化。

199. 二叉树的右视图

• 层序遍历，使用队列。与102不同的是只需一维数组，每次只用把最右面的数加进数组即可。

222. 完全二叉树的节点个数

• 层序遍历，使用队列。遍历每个节点计数器+1.
• 递归。每次调用计算左右子树节点数之和再加1.注意剪枝，因为是完全二叉树，所以递归前可先判断最左侧深度与最右侧深度是否相等。

235. 二叉搜索树的最近公共祖先

• 回溯。从上往下遍历到的第一个在[p,q]区间内的值就是p，q的最近公共祖先。

236. 二叉树的最近公共祖先

• 回溯。需要从底向上遍历，那么便使用后序遍历。单层遍历逻辑：
  • 如果root和p或q相等，或root为空，返回root(终止条件)
  • 如果左节点和右节点都不为空，返回根节点。
  • 如果左子树为空右子树不为空，返回右节点。
  • 如果左子树不为空右子树为空，返回左节点。
  • 若都为空，返回空节点。

429. N叉树的层序遍历

• 层序遍历，每次往队列里面push子节点个数的节点。

450. 删除二叉搜索树中的节点

• 递归
  • 三部曲。
  • 单层递归逻辑有五种
    • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
    • 找到删除的节点
      • 第二种情况：左右孩子都为空，直接删除节点，返回NULL为根节点。
      • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回有孩子为根节点。
      • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点。
      • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头节点放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

513. 找树左下角的值

• 层序遍历，每次遍历记录每层最左边节点数值，当跳出循环时便是树左下角的值。

515. 在每个树行中找最大值

• 层序遍历，每行中取最大值输出。

538. 把二叉搜索树转换为累加树

• 递归。需要一个全局变量pre，用来保存cur节点的前一个节点的数值。单层递归的逻辑：用右中左遍历二叉树。中节点的处理逻辑就是让cur的数值加上前一个节点的数值。

654. 最大二叉树

• 递归。确定终止条件。获得数组最大值，进行分割，构造左子树数组以及右子树数组。用两个数组递归调用函数构造左子树以及右子树。

701. 二叉搜索树中的插入操作

• 递归。终止条件，当前节点为空。单层调用逻辑：当前值小于val，去右子树添加；当前值大于val，去左子树添加。最后返回root。

困难题

七、回溯

简单题

中等题

17. 电话号码的字母组合

• 回溯。首先确定数字字符串对应关系。终止条件为长度相等。for循环条件为对应字符串长度。处理当前节点后，递归调用，再撤销处理结果。

39. 组合总和

• 回溯。与其他组合回溯思想一样。本题数字可重复，每次回溯不必增加startIndex。此外多了一个结束条件为path之和大于target。

40. 组合总和II

• 总体思路相同，不过此题给的candidates数组又重复元素，但每个元素只能取一次并且结果也不能重复。首先对数组排序，使相同的元素挨在一起。去重操作可以将i大于startIndex并且candidates[i] == candidates[i-1]的结果去掉，直接continue。

46. 全排列

• 回溯。使用used数组来记录path里有哪些元素使用了，一个排列里一个元素只能使用一次。

47. 全排列II

• 回溯。类似46，不过需要进一步去重。并且在回溯前需要先对数组进行排序。

77. 组合

• 回溯。同递归三部曲。不过在单层上用for循环横向处理，用回溯纵向处理。先处理当前节点，进行递归，然后撤销处理结果。

90. 子集II

• 回溯。此时没有终止条件，需要遍历整个数组。每个分支可以重复，每层树不可重复。使用set来去重，写在循环体外面。去重首先需要对数组进行排序。

93. 复原IP地址

• 回溯，类似于131，可以根据点个数来写回溯结束条件。每次判断分割是否合适，如果合适就加入点，然后从点后面继续判断。

131. 分割回文串

• 切割问题类似组合问题
  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。

216. 组合总和III

• 回溯。同77题。在处理结束条件时多了一层path中和为sum的逻辑。

491. 递增子序列

• 回溯。同90.此处去重不用排序，排序就全为递增数列了。

困难题

37. 解数独

• 回溯。类似N皇后。

51. N皇后

• 回溯。传递参数chessboard，用row来记录当前遍历到棋盘的第几层，用n来传递棋盘的大小 。注意写isValid函数。

332. 重新安排行程

• 回溯。使用unordered_map<string,map<string,int>>（起飞航班，<落地航班，落地次数>）来记录。

八、贪心算法

简单题

455. 分发饼干

• 贪心算法。对胃口和饼干排序。饼干从小到大向孩子投喂，如果满足便加一。

860. 柠檬水找零

• 贪心算法。维护5，10，20。局部最优：如果是二十先找零10，因为5更加万能。局部最优可以推出全局最优。

1005. K次取反后最大化的数组和

• 贪心算法。先按照绝对值从大到小排序。k尽可能给绝对值大的负数变正。对k有剩余的情况。如果k是单数，对绝对值最小的数取反；如果k是双数，则不变。

中等题

45. 跳跃游戏II

• 贪心算法。遍历数组，每次更新下一步可覆盖最大范围。当遍历到当前可覆盖最大范围还没到达终点时，步数+1，更新当前可覆盖最大范围为下一步可覆盖最大范围。

53. 最大子数组和

• 贪心算法。每次子数组和为0时便丢弃重新计算。因为加上负数只会越来越小。

55. 跳跃游戏

• 贪心算法。每次找能覆盖最大的cover，循环终止条件为cover。

56. 合并区间

• 类似435以及452.

122. 买卖股票的最佳时机II

• 贪心算法。算出每两天的差值，把正数统计起来。

134. 加油站

• 暴力。用两层循环模拟汽车行驶过程。外层循环为初始车站，内层循环为当前车站。
• 从全局贪心。分为三种情况：
  • 情况一：如果gas的综合小于cost总和，那么无论从哪里出发，一定跑不下来。
  • 情况二：rest[i] = gas[i] - cost[i]为一天剩下的油，i从0开始计算累加到最后一战，如果累加没有出现负数，说明从0出发，油就没有断过，说明0就是起点。
  • 情况三：如果累加的最小值是负数，汽车就要从非零结点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。
• 贪心(解法二)：局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

376. 摆动序列

• 贪心算法。删除（可以不管）单调坡度上的节点，使整个序列有最多的局部峰值。

406. 根据身高重建队列

• 贪心。先按照身高排序。局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性；全局最优：最后都做完插入操作，整个队列满足题目队列属性。

435. 无重叠区间

• 贪心。类似452.

452. 用最少数量的箭引爆气球

• 贪心。局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。为了让气球尽可能的重叠，需要对数组进行排序。射中的气球我们对其“进行标记”，具体实现是将重叠气球的右边界统一设置成重叠气球中的最小右边界。

738. 单调递增的数字

• 贪心。一旦出现前一位大于后一位的情况，让前一位减一，后一位设为9.找不出反例，用贪心。从后向前遍历，找到最后一个前一位大于后一位的数，然后后面设置为9.

763. 划分字母区间

• 分为两步
  • 统计每一个字符最后出现的位置
  • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点。

困难题

135. 分发糖果

• 两次贪心。从局部最优推出了全局最优。
  • 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
  • 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

968. 监控二叉树

• 贪心算法。从下往上遍历，叶子结点的父节点安装监控会使用最少二叉树。对每个结点设为三个状态，从下往上遍历，根据子节点情况判断当前是否应该装监控。

九、动态规划

简单题

70. 爬楼梯

• 动态规划
  1. 递推公式： 状态转移方程dp[i] = dp[i - 1] + dp[i - 2]

509. 斐波那契数

• 递归。
• 动态规划
  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. 确定遍历顺序：从前到后遍历。
  5. 举例推导dp数组

746. 使用最小花费爬楼梯

• 动态规划
  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]=1；
  4. 确定遍历顺序：从前到后遍历。
  5. 举例i推导dp数组。

中等题

困难题