担保网站建设,网页设计与制作实训心得体会,学校资源网站建设目标,网站半年了 没有流量动态规划系列5,6,7,8 377 组合总和 Ⅳ未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写)求排列数的题#xff0c;用二维DP过不了#xff1f;自己捋逻辑的话#xff0c;也是可以觉得有漏洞#xff0c;但是怎么修改#xff0c;一下子还没思路用二维DP过不了自己捋逻辑的话也是可以觉得有漏洞但是怎么修改一下子还没思路包括后面的“139. 单词拆分”也是一样的情况。 爬楼梯进阶322 零钱兑换未看解答自己编写的青春版写完这道题后的感受重点代码随想录的代码动态规划也要时刻想着剪枝操作。我的代码(当天晚上理解后自己编写) 279 完全平方数未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写) 一维DP真简单啊动规周总结139 单词拆分未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写)二维DP但是运行错误的代码从DP数组上看可以看出错误但是还没想好怎么改 难道完全背包排列问题只能用一维DP数组去做不过这种问题的通性就是不用刻意往完全背包上套就从动态规划的角度设立一维数组也是能理解代码的。完全背包排列问题传统意义上的二维DP能不能做这里存一个疑问后面再想想其他的完全背包相关问题二维DP是可以做的我在前面也写了。多重背包理论基础代码随想录的代码 背包问题总结篇198 打家劫舍未看解答自己编写的青春版一点感悟重点值得注意的是代码随想录的代码我的代码(当天晚上理解后自己编写) 213 打家劫舍II未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写) 337 打家劫舍 III这道题一定要多练习未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写) 买卖股票系列最重要的就是学会这种DP数组定义方式,dp[i][0]表示第i天持有股票的最大现金dp[i][1]表示第i天不持有股票的最大现金121 买卖股票的最佳时机未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写) 动归周总结122 买卖股票的最佳时机 II未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写) 123 买卖股票的最佳时机 III未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写) 188 买卖股票的最佳时机IV未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写) 309 最佳买卖股票时机含冷冻期买卖股票系列最重要的一道题了学习四种状态的定义持有股票不持有股票但已过冷冻期不持有股票但在冷冻期(换句话说就是前一天卖的)今天卖股票未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写) 动规周总结714 买卖股票的最佳时机含手续费未看解答自己编写的青春版重点代码随想录的代码我的代码(当天晚上理解后自己编写) 关于股票问题想想清楚对于限制只可买卖一次和不限制买卖次数的题目来说dp数组的定义可以是相同的就定义两个状态dp[i][0]:持有股票dp[i][1]:不持有股票都对第0天做单独初始化唯一区别在于在循环中推导 dp[i][0]时需不需要前一天的状态。对于限制最多交易次数的题就按照顺序去定义每一天的状态。含冷冻期的题注意定义的四种状态。股票问题总结篇 377 组合总和 Ⅳ
未看解答自己编写的青春版
这道题简直和上一个系列的最后一题如出一撤。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
class Solution:def combinationSum4(self, nums: List[int], target: int) - int:# 初始化dp数组dp [0]*(target1)# dp数组初始化赋值dp[0] 1# 开始循环因为所求为排列问题最关键的一句话是# 顺序不同的序列被视作不同的组合# 所以遍历顺序是先遍历背包再遍历物品# 下面i这里第一次写的时候忘记从1开始遍历 是从0开始的# 不过我们已经初始化了所以不影响结果for i in range(1,target1):for j in range(len(nums)):if i nums[j]:dp[i] dp[i-nums[j]]return dp[target]重点
一点感悟在做本题时有一点错觉dp数组的含义是没有异议的但是因为题目说不同顺序的排列算作不同的组合那么加入target4当前遍历物品重量为1则dp[4] dp[4-1]假如dp[3]中的方式为[3]那么1加入其中应该有[1,3] [3,1]两种顺序啊不应该是dp[3]再加某个值吗
答不是的这种情况会造成重复在我们的代码编写中物品是按照顺序遍历的上述dp[4] dp[4-1]得到的排列就是[3,1] , 就是这一种情况而[1,3]的情况则在我们遍历到物品3时由dp[4] dp[4-3]得到
本题和上一篇博客的最后一题可谓是相辅相成了这里放上本篇的链接值得细读。
组合总和 Ⅳ
拓展我们在上一篇博客写到了一个爬楼梯问题如果问题改成一次可以爬最多M个台阶求能到达楼顶的方法的个数。
和本题是一模一样的也是求排列数。
代码随想录的代码
class Solution:def combinationSum4(self, nums: List[int], target: int) - int:dp [0] * (target 1) # 创建动态规划数组用于存储组合总数dp[0] 1 # 初始化背包容量为0时的组合总数为1for i in range(1, target 1): # 遍历背包容量for j in nums: # 遍历物品列表if i j: # 当背包容量大于等于当前物品重量时dp[i] dp[i - j] # 更新组合总数return dp[-1] # 返回背包容量为target时的组合总数我的代码(当天晚上理解后自己编写)
过。
求排列数的题用二维DP过不了自己捋逻辑的话也是可以觉得有漏洞但是怎么修改一下子还没思路包括后面的“139. 单词拆分”也是一样的情况。
运行错误的二维DP代码
class Solution:def combinationSum4(self, nums: List[int], target: int) - int:n len(nums)dp [[0]*(target 1) for _ in range(n1)]dp[0][0] 1for i in range(n1):dp[i][0] 1for j in range(target1):dp[0][j] 1for j in range(1, target1):for i in range(1,n1) :dp[i][j] dp[i-1][j]if j nums[i-1] : dp[i][j] dp[i][j-nums[i-1]] return dp[-1][-1]爬楼梯进阶
放上代码随想录的解答链接。 爬楼梯进阶
能想到爬楼梯问题问一共有多少种方法可以看做完全背包求排列数。
322 零钱兑换
未看解答自己编写的青春版
写出来了完全按照动归五部曲做的写完这道题体会到动归五部曲真好用。
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [inf]*(amount1)dp[0] 0for i in range(1,amount1):for j in range(len(coins)):if i coins[j]:dp[i] min(dp[i],dp[i-coins[j]]1)if dp[amount]inf :return -1else :return dp[amount]写完这道题后的感受
做动态规划的题目有时候不需要先把整道题的思路全部想通一步一步来就好就按照动归五部曲这道题一开始我也想不通不知道为什么背包问题求的是最大这里求最小怎么弄。
不用管直接上动归五部曲求最大在递推公式那里就是max运算符求最小在递推公式那里就是min运算符。
第一步确定dp数组的含义题目求什么就定义为什么也别想太多dp[i]定义为amount为 i 时所需要的硬币的最小个数。
第二步确定递推公式这里按照dp数组的定义很容易想到dp[i] min( dp[i] , dp[i-coins[j]] )
第三步初始化。这里很重要也是很容易错的地方。初始化的值和前两步息息相关。一开始我这里就定义错了。 dp[0] 0 , 因为此时没有硬币组合可以是0那么 dp[i] 呢 因为递推公式是求min为了避免初始化对操作符的影响这里应该初始化为最大值一开始我想的是初始化为-1但是这样的话最后的数组依旧全是-1
第四步确定遍历顺序。本题求钱币最小个数那么钱币有顺序和没有顺序都可以都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列。如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。因为{ 5 5 1} 和 { 5 1 5}的钱币个数都是3。我这里的遍历顺序是先遍历的背包不过感觉也许先遍历物品更符合习惯。完全背包问题背包为正序遍历。
第五步模拟打印dp数组。
重点
代码随想录的代码
先遍历物品 后遍历背包
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [float(inf)] * (amount 1) # 创建动态规划数组初始值为正无穷大dp[0] 0 # 初始化背包容量为0时的最小硬币数量为0for coin in coins: # 遍历硬币列表相当于遍历物品for i in range(coin, amount 1): # 遍历背包容量if dp[i - coin] ! float(inf): # 如果dp[i - coin]不是初始值则进行状态转移dp[i] min(dp[i - coin] 1, dp[i]) # 更新最小硬币数量if dp[amount] float(inf): # 如果最终背包容量的最小硬币数量仍为正无穷大表示无解return -1return dp[amount] # 返回背包容量为amount时的最小硬币数量
先遍历物品 后遍历背包优化版 这个剪枝操作还可以。
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [float(inf)] * (amount 1)dp[0] 0for coin in coins:for i in range(coin, amount 1): # 进行优化从能装得下的背包开始计算则不需要进行比较# 更新凑成金额 i 所需的最少硬币数量dp[i] min(dp[i], dp[i - coin] 1)return dp[amount] if dp[amount] ! float(inf) else -1
动态规划也要时刻想着剪枝操作。
我的代码(当天晚上理解后自己编写)
本题首先明确是完全背包问题不要求遍历顺序那么一维DP数组的代码就很好写了。
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [inf]*(amount1)dp[0] 0for i in range(len(coins)):for j in range(coins[i],amount1): dp[j] min(dp[j],dp[j-coins[i]]1)if dp[amount]inf :return -1else :return dp[amount]进阶写个二维DP数组的。
class Solution:def coinChange(self, coins: List[int], amount: int) - int:n len(coins)dp [[inf]*(amount1) for _ in range(n1)]# 二维需要注意的地方真多啊初始化要考虑的更全面dp[0][0] 0for i in range(n1):dp[i][0] 0# 当没有硬币时想要凑成 amount 是不可能的所以不是0而是 inffor i in range(amount1):dp[0][i] 0for i in range(1,n1):# 注意 j 不是从 coins[i-1] 开始而是从 1 开始for j in range(1,amount1): # 注意这里必须要有判断if j coins[i-1]: dp[i][j] dp[i-1][j]else:dp[i][j] min(dp[i-1][j],dp[i][j-coins[i-1]]1)if dp[-1][-1]inf :return -1else :return dp[-1][-1]279 完全平方数
未看解答自己编写的青春版
和上一题差不多本题考虑到如果物品数组也给 [1,n] 的话两个循环时间复杂度就是O(n^2)了那么不如先把可能选择的完全平方数先算出来。
class Solution:def numSquares(self, n: int) - int:items []for i in range(1,int(sqrt(n))2):if i*i n :items.append(i*i)m len(items)dp [inf]*(n1)dp[0] 0for i in range(m):for j in range(items[i],n1):dp[j] min(dp[j],dp[j-items[i]]1)return dp[n]
重点
没啥好说的寻找可选的完全平方数的过程也可以直接放在双重循环里。
本题依然求得是最少的个数的数量所以不管是组合方式还是排列方式均可以所以在遍历顺序上不做要求。
代码随想录的代码
先遍历物品, 再遍历背包
class Solution:def numSquares(self, n: int) - int:dp [float(inf)] * (n 1)dp[0] 0for i in range(1, int(n ** 0.5) 1): # 遍历物品for j in range(i * i, n 1): # 遍历背包# 更新凑成数字 j 所需的最少完全平方数数量dp[j] min(dp[j - i * i] 1, dp[j])return dp[n]我的代码(当天晚上理解后自己编写)
过。
一维DP真简单啊
动规周总结
这周稍微对动态规划有点感觉了。
动规周总结
139 单词拆分
未看解答自己编写的青春版
没思路。
重点
这道题代码随想录写的解答很好其给出的回溯算法也要进行学习相当于回忆知识了。
本题的dp数组的构思递推公式的推导初始化的选择遍历顺序的确定每一步都不容易每一步都容易错
单词拆分
代码随想录的代码
回溯
class Solution:def backtracking(self, s: str, wordSet: set[str], startIndex: int) - bool:# 边界情况已经遍历到字符串末尾返回Trueif startIndex len(s):return True# 遍历所有可能的拆分位置for i in range(startIndex, len(s)):word s[startIndex:i 1] # 截取子串if word in wordSet and self.backtracking(s, wordSet, i 1):# 如果截取的子串在字典中并且后续部分也可以被拆分成单词返回Truereturn True# 无法进行有效拆分返回Falsereturn Falsedef wordBreak(self, s: str, wordDict: List[str]) - bool:wordSet set(wordDict) # 转换为哈希集合提高查找效率return self.backtracking(s, wordSet, 0)DP版本一
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:wordSet set(wordDict)n len(s)dp [False] * (n 1) # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词dp[0] True # 初始状态空字符串可以被拆分成单词for i in range(1, n 1): # 遍历背包for j in range(i): # 遍历单词if dp[j] and s[j:i] in wordSet:dp[i] True # 如果 s[0:j] 可以被拆分成单词并且 s[j:i] 在单词集合中存在则 s[0:i] 可以被拆分成单词breakreturn dp[n]
DP版本二
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:dp [False]*(len(s) 1)dp[0] True# 遍历背包for j in range(1, len(s) 1):# 遍历单词for word in wordDict:if j len(word):dp[j] dp[j] or (dp[j - len(word)] and word s[j - len(word):j])return dp[len(s)]我的代码(当天晚上理解后自己编写)
下面这个代码很好理解
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:dp [False]*(len(s) 1)dp[0] True# 遍历背包for j in range(1, len(s) 1):# 遍历单词for word in wordDict:if j len(word):dp[j] dp[j] or (dp[j - len(word)] and word s[j - len(word):j])return dp[len(s)]二维DP但是运行错误的代码从DP数组上看可以看出错误但是还没想好怎么改
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:n len(wordDict)dp [[False]*(len(s) 1) for _ in range(n1)]dp[0][0] Truefor i in range(n1):dp[i][0] Truefor j in range(1, len(s) 1):for i in range(1,n1) :if j len(wordDict[i-1]):dp[i][j] dp[i-1][j]else :flag dp[i][j-len(wordDict[i-1])] and wordDict[i-1] s[j-len(wordDict[i-1]):j]dp[i][j] dp[i-1][j] or flagreturn dp[-1][-1]难道完全背包排列问题只能用一维DP数组去做不过这种问题的通性就是不用刻意往完全背包上套就从动态规划的角度设立一维数组也是能理解代码的。
完全背包排列问题传统意义上的二维DP能不能做这里存一个疑问后面再想想其他的完全背包相关问题二维DP是可以做的我在前面也写了。
多重背包理论基础
多加一个循环遍历物品个数即可我不喜欢展开成背包问题的写法。同时此题也告诉了我们01背包中的物品可以是相同的。
多重背包理论基础
代码随想录的代码
def test_multi_pack():weight [1, 3, 4]value [15, 20, 30]nums [2, 3, 2]bagWeight 10dp [0] * (bagWeight 1)for i in range(len(weight)): # 遍历物品for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量# 以上为01背包然后加一个遍历个数for k in range(1, nums[i] 1): # 遍历个数if j - k * weight[i] 0:dp[j] max(dp[j], dp[j - k * weight[i]] k * value[i])# 打印一下dp数组for j in range(bagWeight 1):print(dp[j], end )print()print(dp[bagWeight])test_multi_pack()def test_multi_pack(weight, value, nums, bagWeight):dp [0] * (bagWeight 1)for i in range(len(weight)): # 遍历物品for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量# 以上为01背包然后加一个遍历个数for k in range(1, nums[i] 1): # 遍历个数if j - k * weight[i] 0:dp[j] max(dp[j], dp[j - k * weight[i]] k * value[i])# 使用 join 函数打印 dp 数组print( .join(str(dp[j]) for j in range(bagWeight 1)))print(dp[bagWeight])if __name__ __main__:weight [1, 3, 4]value [15, 20, 30]nums [2, 3, 2]bagWeight 10test_multi_pack(weight, value, nums, bagWeight)背包问题总结篇
背包问题结束啦代码随想录对不同问题进行了不同角度的分类用来复习真的很棒。 背包问题总结篇
198 打家劫舍
未看解答自己编写的青春版
依旧是按照五部曲来分析的。
dp数组的含义 考虑到第 i 个房屋包含第 i 个房屋所能偷的最大金额。
class Solution:def rob(self, nums: List[int]) - int:n len(nums)dp [0]*(n1)dp[1] nums[0]for i in range(2,n1):dp[i] max(dp[i-1],dp[i-2]nums[i-1])return dp[n]
一点感悟
目前感觉自己做动态规划类的题目有一个问题就是对dp数组的含义有非常大的执著总觉得要将其定义为一个看上去非常合理的量认为这是求解问题的基础。
但是其实根本不必就是题目问什么就定义什么就好有的问题再适当做一点改变和限制就好。
dp数组的定义不用太纠结dp数组定义的很抽象靠递推关系也可以使状态转移进行的很明朗。
重点
本题其实我多考虑了一个无用状态 dp[0] 因为在我的定义中i 是代表第 i 个房屋而房屋下标的开始就是1. 在代码随想录的讲解中i 是代表下标为 i 为房屋这样就可以从0开始了不过我这样初始化好像更简单一些。
dp[i] 仅仅是考虑到第 i 个房屋不考虑偷与不偷偷与不偷通过递推公式去考虑而不是代表偷第 i 个房屋。在dp定义中显示地考虑每个房间偷与不偷状态的数组为二维dp数组。
值得注意的是
像我对本题dp数组的定义方式还是不如代码随想录中给出的这一点在下一题就有所体现如果所有房屋组成了一个环那么我就不能在前面硬生生加入一个dp[0]了还是要按照房屋下标去考虑。
代码随想录的代码
1维DP
class Solution:def rob(self, nums: List[int]) - int:if len(nums) 0: # 如果没有房屋返回0return 0if len(nums) 1: # 如果只有一个房屋返回其金额return nums[0]# 创建一个动态规划数组用于存储最大金额dp [0] * len(nums)dp[0] nums[0] # 将dp的第一个元素设置为第一个房屋的金额dp[1] max(nums[0], nums[1]) # 将dp的第二个元素设置为第一二个房屋中的金额较大者# 遍历剩余的房屋for i in range(2, len(nums)):# 对于每个房屋选择抢劫当前房屋和抢劫前一个房屋的最大金额dp[i] max(dp[i - 2] nums[i], dp[i - 1])return dp[-1] # 返回最后一个房屋中可抢劫的最大金额2维DP
class Solution:def rob(self, nums: List[int]) - int:if not nums: # 如果没有房屋返回0return 0n len(nums)dp [[0, 0] for _ in range(n)] # 创建二维动态规划数组dp[i][0]表示不抢劫第i个房屋的最大金额dp[i][1]表示抢劫第i个房屋的最大金额dp[0][1] nums[0] # 抢劫第一个房屋的最大金额为第一个房屋的金额for i in range(1, n):dp[i][0] max(dp[i-1][0], dp[i-1][1]) # 不抢劫第i个房屋最大金额为前一个房屋抢劫和不抢劫的最大值dp[i][1] dp[i-1][0] nums[i] # 抢劫第i个房屋最大金额为前一个房屋不抢劫的最大金额加上当前房屋的金额return max(dp[n-1][0], dp[n-1][1]) # 返回最后一个房屋中可抢劫的最大金额优化版
class Solution:def rob(self, nums: List[int]) - int:if not nums: # 如果没有房屋返回0return 0prev_max 0 # 上一个房屋的最大金额curr_max 0 # 当前房屋的最大金额for num in nums:temp curr_max # 临时变量保存当前房屋的最大金额curr_max max(prev_max num, curr_max) # 更新当前房屋的最大金额prev_max temp # 更新上一个房屋的最大金额return curr_max # 返回最后一个房屋中可抢劫的最大金额
我的代码(当天晚上理解后自己编写)
过。
213 打家劫舍II
未看解答自己编写的青春版
没写出来被环形房屋卡住了纠结在于怎样处理第0个和第n个之间的关系。
错误代码中的定义dp[i][0] : 没偷第0个包括第 i 个房屋所能获得的最大金币。dp[i][1] : 偷第0个包括第 i 个房屋所能获得的最大金币。
class Solution:def rob(self, nums: List[int]) - int:n len(nums)dp [[0]*2 for _ in range(n)]dp[0][0] 0dp[0][1] nums[0]dp[1][0] nums[1]dp[1][1] nums[0]for i in range(2,n):dp[i][0] max(dp[i-1][0],dp[i-2][0]nums[i])dp[i][1] dp[i-1][1]return max(dp[n-1])我这个错误的代码打印一下dp数组就可以明显看出错误。思考了一下应该没得改这种dp数组的定义方式就是错误的带有全局意义的变量不能将某一个元素的特性赋给它。
重点
还是思考方向错了直接暴力区分考虑首元素不考虑尾元素考虑尾元素不考虑首元素两种逻辑即可。说白了就是上一题的逻辑跑两遍每次传入的房间数组分别是去除尾元素和去除首元素的然后取最大即可。
解决环的问题分情况讨论。
环形问题使我们找不到起始位置要考虑将环形问题展开展开为线性问题。
代码随想录的代码
class Solution:def rob(self, nums: List[int]) - int:if len(nums) 0:return 0if len(nums) 1:return nums[0]result1 self.robRange(nums, 0, len(nums) - 2) # 情况二result2 self.robRange(nums, 1, len(nums) - 1) # 情况三return max(result1, result2)# 198.打家劫舍的逻辑def robRange(self, nums: List[int], start: int, end: int) - int:if end start:return nums[start]prev_max nums[start]curr_max max(nums[start], nums[start 1])for i in range(start 2, end 1):temp curr_maxcurr_max max(prev_max nums[i], curr_max)prev_max tempreturn curr_max2维DP
class Solution:def rob(self, nums: List[int]) - int:if len(nums) 3:return max(nums)# 情况二不抢劫第一个房屋result1 self.robRange(nums[:-1])# 情况三不抢劫最后一个房屋result2 self.robRange(nums[1:])return max(result1, result2)def robRange(self, nums):dp [[0, 0] for _ in range(len(nums))]dp[0][1] nums[0]for i in range(1, len(nums)):dp[i][0] max(dp[i - 1])dp[i][1] dp[i - 1][0] nums[i]return max(dp[-1])
优化版
class Solution:def rob(self, nums: List[int]) - int:if not nums: # 如果没有房屋返回0return 0if len(nums) 1: # 如果只有一个房屋返回该房屋的金额return nums[0]# 情况二不抢劫第一个房屋prev_max 0 # 上一个房屋的最大金额curr_max 0 # 当前房屋的最大金额for num in nums[1:]:temp curr_max # 临时变量保存当前房屋的最大金额curr_max max(prev_max num, curr_max) # 更新当前房屋的最大金额prev_max temp # 更新上一个房屋的最大金额result1 curr_max# 情况三不抢劫最后一个房屋prev_max 0 # 上一个房屋的最大金额curr_max 0 # 当前房屋的最大金额for num in nums[:-1]:temp curr_max # 临时变量保存当前房屋的最大金额curr_max max(prev_max num, curr_max) # 更新当前房屋的最大金额prev_max temp # 更新上一个房屋的最大金额result2 curr_maxreturn max(result1, result2)我的代码(当天晚上理解后自己编写)
过。
337 打家劫舍 III
这道题一定要多练习
未看解答自己编写的青春版
超出时间限制代码思路是代码随想录中的暴力递归版。
class Solution:def rob(self, root: Optional[TreeNode]) - int:if root None :return 0if root.left None and root.right 0:return root.valleft self.rob(root.left)right self.rob(root.right)if left 0 and right 0 :return root.valelif left 0 and right ! 0 :return max(root.valself.rob(root.right.left)self.rob(root.right.right),right)elif left ! 0 and right 0 :return max(root.valself.rob(root.left.left)self.rob(root.left.right),left)else :return max(root.valself.rob(root.left.left)self.rob(root.left.right)self.rob(root.right.left)self.rob(root.right.right),leftright)重点
代码随想录给出的博文中分析了暴力递归超时的原因许多节点的状态被重复计算了进而给出解决方案用两个维度去记录当前节点的状态
这是我没想到的。
本题的解答博文中还涉及了记忆化递归的过程这个在之前应该是没有讲过的(虽然卡哥说他讲过了)看了看代码其实就是维护一个字典来储存已经算过的子串代码上也很好理解在递归函数一开始判断那里加上 if 存在 就 return . 递归结束有了值就加入字典。
本题是一个树形DP的入门题要学习放上代码随想录的解答博文链接。 打家劫舍 III–树形DP
注意本题的dp数组其实就是一个一维的数组而且长度为2就表示当前节点的状态偷与不偷不需要去定义包含所有节点的dp数组因为在递归过程中每一次递归都会有一个相应的dp数组存在。
代码随想录的代码
暴力递归
class Solution:def rob(self, root: TreeNode) - int:if root is None:return 0if root.left is None and root.right is None:return root.val# 偷父节点val1 root.valif root.left:val1 self.rob(root.left.left) self.rob(root.left.right)if root.right:val1 self.rob(root.right.left) self.rob(root.right.right)# 不偷父节点val2 self.rob(root.left) self.rob(root.right)return max(val1, val2)记忆化递归
class Solution:memory {}def rob(self, root: TreeNode) - int:if root is None:return 0if root.left is None and root.right is None:return root.valif self.memory.get(root) is not None:return self.memory[root]# 偷父节点val1 root.valif root.left:val1 self.rob(root.left.left) self.rob(root.left.right)if root.right:val1 self.rob(root.right.left) self.rob(root.right.right)# 不偷父节点val2 self.rob(root.left) self.rob(root.right)self.memory[root] max(val1, val2)return max(val1, val2)动态规划
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def rob(self, root: Optional[TreeNode]) - int:# dp数组dp table以及下标的含义# 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱# 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱dp self.traversal(root)return max(dp)# 要用后序遍历, 因为要通过递归函数的返回值来做下一步计算def traversal(self, node):# 递归终止条件就是遇到了空节点那肯定是不偷的if not node:return (0, 0)left self.traversal(node.left)right self.traversal(node.right)# 不偷当前节点, 偷子节点# 子节点偷不偷决定于哪个值更大val_0 max(left[0], left[1]) max(right[0], right[1])# 偷当前节点, 不偷子节点val_1 node.val left[0] right[0]return (val_0, val_1)我的代码(当天晚上理解后自己编写)
一定要多练习这道题。
买卖股票系列最重要的就是学会这种DP数组定义方式,dp[i][0]表示第i天持有股票的最大现金dp[i][1]表示第i天不持有股票的最大现金
121 买卖股票的最佳时机
未看解答自己编写的青春版
解答错误错在无法明确股票是在哪一天买入和卖出的在递推公式上就会出现错误和混乱。 错误的dp数组含义在前 i 天买入卖出所得的最大金钱。
class Solution:def maxProfit(self, prices: List[int]) - int:dp [0]*len(prices)dp[0]-infdp[1]prices[1]-prices[0]for i in range(2,len(prices)):temp [dp[i-1],dp[i-1]-prices[i-1]prices[i],prices[i]-prices[i-1]]dp[i] max(temp)print(dp)return dp[len(prices)-1]又想了想想出了一个自己觉得就很垃圾的方案。 dp数组含义在第 i 天卖出所得的最大金钱。在本题中初始化同样需要注意本题的示例中已说明如果没有交易完成return 0 。同样的要首先判断一下 prices 数组是不是只有一个值一个值也要return 0。在我的定义下对于dp[0]可以不做初始化因为这种情况是非法的而且我在前面已经做了 if 判断。
我这个方法最后还要对dp数组取一个max
class Solution:def maxProfit(self, prices: List[int]) - int:if len(prices)1:return 0dp [0]*len(prices)dp[1]prices[1]-prices[0]for i in range(2,len(prices)):temp [dp[i-1]-prices[i-1]prices[i],prices[i]-prices[i-1]]dp[i] max(temp)return max(dp)重点
本题还有一个很朴素的贪心法。因为股票就买卖一次那么贪心的想法很自然就是取最左最小值取最右最大值那么得到的差值就是最大利润。
跟股票买卖有关的问题dp数组的定义基本都是从本题定义的基础上演变过去的。还是要学习代码随想录这一套定义dp数组的方法的我的那种方法可能只能解决这一道题不具有普适性。 本题的初始化也是需要理解的。
代码随想录的代码
贪心法
class Solution:def maxProfit(self, prices: List[int]) - int:low float(inf)result 0for i in range(len(prices)):low min(low, prices[i]) #取最左最小价格result max(result, prices[i] - low) #直接取最大区间利润return result动态规划版本一
class Solution:def maxProfit(self, prices: List[int]) - int:length len(prices)if len 0:return 0dp [[0] * 2 for _ in range(length)]dp[0][0] -prices[0]dp[0][1] 0for i in range(1, length):dp[i][0] max(dp[i-1][0], -prices[i])dp[i][1] max(dp[i-1][1], prices[i] dp[i-1][0])return dp[-1][1]动态规划版本二
class Solution:def maxProfit(self, prices: List[int]) - int:length len(prices)dp [[0] * 2 for _ in range(2)] #注意这里只开辟了一个2 * 2大小的二维数组dp[0][0] -prices[0]dp[0][1] 0for i in range(1, length):dp[i % 2][0] max(dp[(i-1) % 2][0], -prices[i])dp[i % 2][1] max(dp[(i-1) % 2][1], prices[i] dp[(i-1) % 2][0])return dp[(length-1) % 2][1]动态规划版本三
class Solution:def maxProfit(self, prices: List[int]) - int:length len(prices)dp0, dp1 -prices[0], 0 #注意这里只维护两个常量因为dp0的更新不受dp1的影响for i in range(1, length):dp1 max(dp1, dp0 prices[i])dp0 max(dp0, -prices[i])return dp1我的代码(当天晚上理解后自己编写)
过。
动归周总结
代码随想录的博文总结的很好。
动归周总结
122 买卖股票的最佳时机 II
这道题用上一题我的dp数组定义就行不通了。
所以还是学习代码随想录定义的dp数组含义吧。
未看解答自己编写的青春版
借鉴了上一题代码随想录的dp数组定义本题只改变了递推逻辑的部分。
class Solution:def maxProfit(self, prices: List[int]) - int:length len(prices)if len 0 or len(prices)1:return 0dp [[0] * 2 for _ in range(length)]dp[0][0] -prices[0]dp[0][1] 0for i in range(1,length):dp[i][0] max(dp[i-1][1]-prices[i],dp[i-1][0])dp[i][1] max(dp[i-1][0]prices[i],dp[i-1][1])return dp[length-1][1]重点
本题是股票可以买卖多次上一题股票只能买卖一次。注意体会两题的区别。其他诸如dp数组的含义以及dp数组的初始化问题都是一样的。 代码随想录的代码
版本一
class Solution:def maxProfit(self, prices: List[int]) - int:length len(prices)dp [[0] * 2 for _ in range(length)]dp[0][0] -prices[0]dp[0][1] 0for i in range(1, length):dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i]) #注意这里是和121. 买卖股票的最佳时机唯一不同的地方dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])return dp[-1][1]
版本二
class Solution:def maxProfit(self, prices: List[int]) - int:length len(prices)dp [[0] * 2 for _ in range(2)] #注意这里只开辟了一个2 * 2大小的二维数组dp[0][0] -prices[0]dp[0][1] 0for i in range(1, length):dp[i % 2][0] max(dp[(i-1) % 2][0], dp[(i-1) % 2][1] - prices[i])dp[i % 2][1] max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] prices[i])return dp[(length-1) % 2][1]
我的代码(当天晚上理解后自己编写)
过。
123 买卖股票的最佳时机 III
未看解答自己编写的青春版
依旧根据前面两题的逻辑思维。要注意的是本来我想在二维数组后面再加一维来表示当前是第几次购买的状态但是三维数组可能在声明上不太方便了于是就按照代码随想录中的做法把第三维压缩进第二维了这样写法也挺好的也很清晰明了。
本题的dp数组定义不需要变化只要明确定义4个状态就好需要注意的是初始值的状态这里我就在第一次提交时出错了。
就是第0天第二次持有的状态下所拥有的最大金钱数应该和第0天第一次持有的状态相同均为 -prices[0] 。 表示当天买入-卖出-买入。一开始我这里设置为0了产生错误。
class Solution:def maxProfit(self, prices: List[int]) - int:n len(prices)if n0 or n1:return 0dp [[0]*4 for _ in range(n)]dp[0][0] -prices[0]dp[0][1] 0dp[0][2] -prices[0]dp[0][3] 0for i in range(1,n):dp[i][0] max(dp[i-1][0],-prices[i])dp[i][1] max(dp[i-1][1],dp[i-1][0]prices[i])dp[i][2] max(dp[i-1][2],dp[i-1][1]-prices[i])dp[i][3] max(dp[i-1][3],dp[i-1][2]prices[i])return max(dp[n-1][1],dp[n-1][3])重点
就是定义四个状态从来没想过定义一个0状态。 这里不做什么记录了放上代码随想录的链接。 买卖股票的最佳时机 III
有一点需要学习的地方 最大的时候一定是卖出的状态而两次卖出的状态现金最大一定是最后一次卖出。如果想不明白的录友也可以这么理解如果第一次卖出已经是最大值了那么我们可以在当天立刻买入再立刻卖出。所以dp[n][4]已经包含了dp[n][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。
代码随想录的代码
版本一
class Solution:def maxProfit(self, prices: List[int]) - int:if len(prices) 0:return 0dp [[0] * 5 for _ in range(len(prices))]dp[0][1] -prices[0]dp[0][3] -prices[0]for i in range(1, len(prices)):dp[i][0] dp[i-1][0]dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i])dp[i][3] max(dp[i-1][3], dp[i-1][2] - prices[i])dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i])return dp[-1][4]版本二
class Solution:def maxProfit(self, prices: List[int]) - int:if len(prices) 0:return 0dp [0] * 5 dp[1] -prices[0]dp[3] -prices[0]for i in range(1, len(prices)):dp[1] max(dp[1], dp[0] - prices[i])dp[2] max(dp[2], dp[1] prices[i])dp[3] max(dp[3], dp[2] - prices[i])dp[4] max(dp[4], dp[3] prices[i])return dp[4]我的代码(当天晚上理解后自己编写)
过。
188 买卖股票的最佳时机IV
未看解答自己编写的青春版
同样的就是上一题的简单拓展但这里我觉得我自己对在遍历中的第1次买入也就是index为0的操作有些冗余我是用一个 if 条件去单独判断的。不知道代码随想录中怎么写。
class Solution:def maxProfit(self, k: int, prices: List[int]) - int:n len(prices)if n0 or n1:return 0m int(k*2)dp [[0]*m for _ in range(n)]for i in range(m):if i %2 0:dp[0][i] -prices[0]for i in range(1,n):for j in range(m):if j % 2 0:if j 0 :dp[i][j] max(dp[i-1][j],-prices[i])else :dp[i][j] max(dp[i-1][j],dp[i-1][j-1]-prices[i])else :dp[i][j] max(dp[i-1][j],dp[i-1][j-1]prices[i])return dp[n-1][m-1]重点
代码随想录对上述我提到的问题的解决方法是多定义一个状态0贯穿始终始终不变一直为0 。
代码随想录的代码
版本一
class Solution:def maxProfit(self, k: int, prices: List[int]) - int:if len(prices) 0:return 0dp [[0] * (2*k1) for _ in range(len(prices))]for j in range(1, 2*k, 2):dp[0][j] -prices[0]for i in range(1, len(prices)):for j in range(0, 2*k-1, 2):dp[i][j1] max(dp[i-1][j1], dp[i-1][j] - prices[i])dp[i][j2] max(dp[i-1][j2], dp[i-1][j1] prices[i])return dp[-1][2*k]
版本二 class Solution:def maxProfit(self, k: int, prices: List[int]) - int:if len(prices) 0: return 0dp [0] * (2*k 1)for i in range(1,2*k,2):dp[i] -prices[0]for i in range(1,len(prices)):for j in range(1,2*k 1):if j % 2:dp[j] max(dp[j],dp[j-1]-prices[i])else:dp[j] max(dp[j],dp[j-1]prices[i])return dp[2*k]
我的代码(当天晚上理解后自己编写)
过。
309 最佳买卖股票时机含冷冻期
买卖股票系列最重要的一道题了学习四种状态的定义持有股票不持有股票但已过冷冻期不持有股票但在冷冻期(换句话说就是前一天卖的)今天卖股票
未看解答自己编写的青春版
我还是对上一题的思路稍加修改先算出了最大的K值但是这样的后果就是不管是时间还是占用内存上均只击败了5%的用户。
class Solution:def maxProfit(self, prices: List[int]) - int:n len(prices)if n0 or n1:return 0k (n//3)1m int(k*2)dp [[0]*m for _ in range(n)]for i in range(m):if i %2 0:dp[0][i] -prices[0]for i in range(1,n):for j in range(m):if j % 2 0:if j 0 :dp[i][j] max(dp[i-1][j],-prices[i])else :dp[i][j] max(dp[i-1][j],dp[i-2][j-1]-prices[i])else :dp[i][j] max(dp[i-1][j],dp[i-1][j-1]prices[i])return dp[n-1][m-1]重点
买卖K次那个题没办法必须定义那么多状态但是对于本题其实只要定义4个状态就可以了去学习代码随想录的题解。
要灵活啊谁说买卖多次就必须要有循环了只有最多买卖K次需要再套一层循环前面也做了无限次买卖的题了不也只有外面一层循环 代码随想录的代码
class Solution:def maxProfit(self, prices: List[int]) - int:n len(prices)if n 0:return 0dp [[0] * 4 for _ in range(n)]dp[0][0] -prices[0] #持股票for i in range(1, n):dp[i][0] max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i])dp[i][1] max(dp[i-1][1], dp[i-1][3])dp[i][2] dp[i-1][0] prices[i]dp[i][3] dp[i-1][2]return max(dp[n-1][3], dp[n-1][1], dp[n-1][2])我的代码(当天晚上理解后自己编写)
过。
动规周总结
四道买卖股票题目总结。
动规周总结
714 买卖股票的最佳时机含手续费
未看解答自己编写的青春版
在卖股票的时候把手续费减去就好了注意初始化那里第0天不持有股票依然返回0不买不卖而不是一个负数因为求的是最大值。
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:length len(prices)if len 0 or len(prices)1:return 0dp [[0] * 2 for _ in range(length)]dp[0][0] -prices[0]dp[0][1] 0for i in range(1,length):dp[i][0] max(dp[i-1][1]-prices[i],dp[i-1][0])dp[i][1] max(dp[i-1][0]prices[i]-fee,dp[i-1][1])return dp[length-1][1]重点
这道题要掌握的方法还有一个贪心法动态规划方法没什么新意但是不知道为什么这道题贪心法的解答博客竟然没有在话题目录里。
贪心法还要理解一下时间原因没细看。
动态规划思路
贪心思路
代码随想录的代码
动态规划
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:n len(prices)dp [[0] * 2 for _ in range(n)]dp[0][0] -prices[0] #持股票for i in range(1, n):dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i])dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i] - fee)return max(dp[-1][0], dp[-1][1])贪心法
class Solution: # 贪心思路def maxProfit(self, prices: List[int], fee: int) - int:result 0minPrice prices[0]for i in range(1, len(prices)):if prices[i] minPrice: # 此时有更低的价格可以买入minPrice prices[i]elif prices[i] (minPrice fee): # 此时有利润同时假买入高价的股票看看是否继续盈利result prices[i] - (minPrice fee)minPrice prices[i] - feeelse: # minPrice prices[i] minPrice fee 价格处于minPrice和minPricefee之间不做操作continuereturn result我的代码(当天晚上理解后自己编写)
过
关于股票问题想想清楚对于限制只可买卖一次和不限制买卖次数的题目来说dp数组的定义可以是相同的就定义两个状态dp[i][0]:持有股票dp[i][1]:不持有股票都对第0天做单独初始化唯一区别在于在循环中推导 dp[i][0]时需不需要前一天的状态。
对于限制最多交易次数的题就按照顺序去定义每一天的状态。
含冷冻期的题注意定义的四种状态。
股票问题总结篇
股票问题总结篇
