学无止境

# 问题描述 # 思路与题解 这个题真是我的克星啊，不知道为什么，我脑子一直转不过弯来，总是会想着，要是中间有个小的负数把可以合成一个更大的连续数组隔开了怎么办，该怎么判断，我就一直死脑筋卡在这里了，感觉我也是有点笨笨的，呜呜呜～ 但言归正传，看了官方题解后，发现我就真是没转过那个弯来，你就管他是不是一个小负数会把更大的数组隔开，反正只要判断当前数的前面，前面数组的连续和是否对该数有帮助不就行了，有帮助我就收为我有（nums [i] + prev），没有帮助我就另起炉灶（nums...

# 题目描述 # 思路与题解 这题我承认我没有解出来，还是看了官方题解后才有思路的 🤣 怎么说呢，这道题如果你能转过弯，把它映射到我们前几道题所做的打家劫舍上，那这个题就很简单啦，关键就在于如何把这个题转换为打家劫舍～ 再看一遍题干， 你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素 ，意思不就是如果我们要获取 nums [i] 房屋的财产，那就不能获取 nums [i] 相邻两间房屋的财产了，所以我们的思路就是要把相同点数 i 累加起来，作为 nums [i]...

# 题目描述 # 思路与题解 比上一题多加了一些条件，但动态规划的思想不变，都是先求解子问题（小问题），然后逐步求解出一个复杂的问题（大问题）~ 上一题我们可以知道在当前 i 处能走到的最大距离，所以稍微一思考，只要后面走的距离在这最大距离之内，步数都不变；只有能走的最大距离不能满足 i 了，才把步数加一，同时更新 i 处能走到的最大距离，是不是很 easy~ class Solution {public: int jump(vector<int>& nums) { int n = nums.size(); if...

# 题目描述 # 思路与题解 经过前面几道题的熏陶，这类题感觉已经挺熟练了，动态规划就是先求解子问题，比如说一个长数组，我们先不要看那么多元素，可以就从有一个元素开始往后遍历求解，最后就可以求出一个复杂问题的答案了～～ 但是这题应该还有好多其他解法，比如说深度优先搜索应该也算一种，一直往前冲，冲不动了就回退，然后再往前冲～～ class Solution {public: bool canJump(vector<int>& nums) { int n = nums.size(); int limit = 0;...

# 题目描述 # 思路与题解 这道题看起来不难，不就在上一道题的基础上添加了首尾房间相邻的限制吗，但我尝试解了三次都失败了，太丢人了...

# 题目描述 # 思路与题解 和前面题的思路蛮像的，关键在于比大小，因为题目有不能偷盗相邻的两个房间的限制，所以比大小的关键就是 max(dp[i-1], dp[i-2] + nums[i]) ，dp [i] 就表示新增了第 i 个房间后的最大收益，所以如果我第 i 个房间不偷，我能得到的最大收益就是 dp [i-1]；如果我第 i 个房间偷了，那我 i-1 房间就不能偷了，所以我能得的最大收益就是 dp [i-2] + nums [i]，是不是很 easy~~ 当然啦，再稍微思考一下，可以用滚动数组把空间复杂度优化为 O (1) class Solution...

# 题目描述 # 思路与题解 这个题目描述的比较绕，如果有纸和笔的话，在纸上画一画会好很多，比如我胡乱画的如下 看了官方题解，思路才比较清晰了 上述代码的时间复杂度和空间复杂度都是 O (n)。但也可以用滚动数组的方式将空间复杂度优化到 O (1) class Solution {public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); int res[n+1]; res[0] = res[1] = 0; res[2]...

# 题目描述 # 思路与题解 n 阶，可以看成是 n-2 阶爬 2 阶后到达，也可以看成是 n-1 阶爬 1 阶后到达，所以就是 n-2 阶的爬取数 + n-1 阶的爬取数，翻译过来就是斐波那契数，easy~ class Solution {public: int climbStairs(int n) { //n 阶，可以看成是 n-2 阶爬 2 阶后到达 // 也可以看成是 n-1 阶爬 1 阶后到达 // 所以就是 n-2 阶的爬取数 + n-1 阶的爬取数 // 翻译过来就是斐波那契数，easy if (n < 4) return...

# 题目描述 # 思路与题解 和昨天的斐波那契数思路一样，用滚动数组的思想，关键点在于设置 p、q、t、r 的初值，我们知道，r = p + q + t，第一个要计算的值是 Fn (3)，T_3 = 0 + 1 + 1，这是滚动之后的，所以 p、q、t、r 的初值应该是 0、0、1、1，这样滚动过后才能变成 0、1、1，就能算出 Fn (3) = r = 0 + 1 + 1。Easy~ class Solution {public: int tribonacci(int n) { if (n < 2) return n; if (n ==...

# 题目描述 # 思路与题解 第一想到的应该就是递归，用递归尝试后爆溢栈了，于是便想到用一个数组记录下来已算出的斐波那契数。我犯的一个低级错误就是把 if (n == 1 || n == 0) return n; 刚开始没有放到 fib 函数里，导致系统输入 0 时，直接 n - 1 = -1，数组越界报错了 🤣 长时间不思考果然脑袋就变笨了 看了官方题解后又有了收获，用滚动数组的思想，就可以将递归函数转换为 for 循环，用自下而上的方法去求解子问题，秒的很 class Solution {public: int data[31]; bool flag[31];...