打家劫舍/股票问题/爬楼梯问题v2"/>
背包问题/打家劫舍/股票问题/爬楼梯问题v2
leetcode-买卖股票/背包问题_MaYingColdPlay的博客-CSDN博客
leetcode-记忆化深搜/动态规划v1_林冲风雪山神庙的博客-CSDN博客_leetcode记忆化搜索
零钱兑换问题总结：
零钱兑换两个题是完全背包问题。
零钱兑换1在深搜的时候只考虑amount就行，因为是问最小次数，不用统计次数总和，因此，不用考虑硬币顺序。在dp的时候第一层循环是amount,第二层循环是coins。
零钱兑换2在深搜的时候要考虑下标和amount，因为问的是组合数，因此要考虑顺序。在dp的时候第一层循环是coins,第二层循环是amount。
dp的本质也是枚举，对于零钱兑换2来说，其递推关系式：
dp = [0 for _ in range(amount+1)]
dp[0] = 1
for i in range(len(coins)):
for j in range(amount+1):
if j >= coins[i]:
dp[j] += dp[j-coins[i]]
return dp[-1]
枚举到了所有的情况。
01背包问题dp写法
二维dp
一维dp
代码随想录
背包问题
01背包
474 一和零
深搜
class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:def count(ss):count1=0count0=0for s in ss:if s=="1":count1+=1else:count0+=1return count1,count0@lru_cache(None)def dfs(index,cur_m,cur_n):if index>len(strs)-1:return 0#不选当前a1=dfs(index+1,cur_m,cur_n)#选当前count1,count0=count(strs[index])a2=0if cur_m+count0<=m and cur_n+count1<=n:a2=dfs(index+1,cur_m+count0,cur_n+count1)+1return max(a1,a2)return dfs(0,0,0)动态规划
class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:length = len(strs)dp = [[[0] * (n+1) for _ in range(m+1)] for _ in range(length+1)]for i in range(1, length+1):c0 = strs[i-1].count('0') # 当前字符串中0的数目c1 = len(strs[i-1]) - c0 # 当前字符串中1的数目for j in range(m+1): # 第二层循环：0的背包容量for k in range(n+1): # 第三层循环：1的背包容量if j < c0 or k < c1: # 无法添加当前字符串dp[i][j][k] = dp[i-1][j][k]else: # 可选或不选当前字符串，取两者之间的较大值dp[i][j][k] = max( dp[i-1][j][k], dp[i-1][j-c0][k-c1] + 1 )return dp[length][m][n]作者：flix
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};494 目标和
深搜
注意这个题cache的设计，是把下标和当前值合并起来。
def findTargetSumWays_v3(nums,target):def dfs(i,cur):key=str(i)+'_'+str(cur)if key in cache:return cache[key]if i==len(nums):if cur==target:return 1else:return 0#下一层是加或者减下一个数left=dfs(i+1,cur+nums[i])right=dfs(i+1,cur-nums[i])cache[key]=left+rightreturn left+rightcache={}return dfs(0,0)# nums=[1,2]
# target=3nums=[1,1,1,1,1]
target=3
res=findTargetSumWays_v3(nums,target)
print(res)动态规划
同分割等和子集：
力扣
class Solution(object):def findTargetSumWays(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""# dp[i][j],表示前i个元素，和为j的方法数positive_sum = (sum(nums) + target) // 2if (sum(nums) + target) % 2 > 0:return 0if positive_sum < 0:return 0dp = [[0 for _ in range(positive_sum+1)] for _ in range(len(nums)+1)]# 当没有任何元素可以选取时，元素和只能是 0dp[0][0] = 1for i in range(1,len(nums)+1):for j in range(positive_sum+1):if j < nums[i-1]:dp[i][j] = dp[i-1][j]else:dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]# print(dp)return dp[-1][-1]416 分割等和子集
力扣
力扣
class Solution:def canPartition(self, nums: List[int]) -> bool:if sum(nums)%2 or len(nums) < 2: return Falsehalf = sum(nums)//2nums.sort(reverse = True)if nums[0] > half: return False@lru_cache(None)def dfs(target, i):if target == nums[i]: return Trueif target > nums[i]:for j in range(i+1, len(nums)):if dfs(target-nums[i], j):return Truereturn Falsereturn dfs(half, 0)作者：dangerusswilson
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。记忆化深搜
转移方程就是dfs i+1 加或者不加的和 任意一个为真就行
class Solution:def canPartition(self, nums: List[int]) -> bool:if sum(nums)%2 !=0:return Falsehalf = sum(nums) //2# nums.sort()@lru_cache(None)def dfs(index, cur_sum):if cur_sum>half:return Falseelif cur_sum == half:return Trueelif index >= len(nums):return Falsereturn dfs(index + 1, cur_sum + nums[index]) or dfs(index + 1, cur_sum)# a1 = dfs(index + 1, cur_sum + nums[index])# a2 = dfs(index + 1, cur_sum)# return a1 or a2return dfs(0, 0)698划分为k个相等的子集
回溯
力扣
回溯算法牛逼！
class Solution:def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:#不连续，枚举分割点肯定不行。因此要用回溯#枚举筒的index和nums的index，这个筒放不放nums[i]，k*2**nif sum(nums) % k > 0:return Falsetarget = sum(nums) // ktong = [0 for _ in range(k)]used = [False for _ in range(len(nums))]nums.sort(reverse=True)# @lru_cache(None) #还有一个状态used.cache不到，所以这种写法不能做cachedef dfs(k_index, nums_index):if nums_index > len(nums) - 1:return Falseif k_index == k:return Truefor i in range(nums_index, len(nums)):if used[i] == False:# i放k_index里if tong[k_index] + nums[i] < target:tong[k_index] += nums[i]used[i] = Trueif dfs(k_index, i + 1):return Truetong[k_index] -= nums[i]used[i] = False# 放满了，下一个筒从0开始遍历elif tong[k_index] + nums[i] == target:tong[k_index] += nums[i]used[i] = Trueif dfs(k_index+1, 0):return Truetong[k_index] -= nums[i]used[i] = Falsereturn Falsereturn dfs(0, 0)状压dp
状态压缩dfs的思路是和回溯一样的，优点在于可以cache，因此速度会快。
回溯解法，dfs(k_index, nums_index)，还有一个状态列表used，cache不到。
通过这个题理解了回溯和深搜的区别，见有道云笔记里。
class Solution:def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:s = sum(nums)if s % k != 0:#如果不能平分为k个集合的话,直接返回Falsereturn False q = s // k #每个集合的总和l = len(nums)@lru_cache(None)def dfs(state, n, c):if c == k:return Truefor i in range(l):if state & (1 << i) == 0:if n + nums[i] < q:if dfs(state | (1 << i), n + nums[i], c):return Trueelif n + nums[i] == q:if dfs(state | (1 << i), 0, c + 1):return Truereturn Falsereturn dfs(0, 0, 0)
1049. 最后一块石头的重量 II
class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:#转化为01背包。target是 half = sum(stones) // 2#找最接近half的值half = sum(stones) //2@lru_cache(None)def dfs(index,cur_sum):if index == len(stones):return abs(half - cur_sum)return min(dfs(index+1,cur_sum + stones[index]),dfs(index+1,cur_sum))tmp_res = dfs(0,0)a = half - tmp_resb = sum(stones) - areturn b - a2044. 统计按位或能得到最大值的子集数目
class Solution:def countMaxOrSubsets(self, nums: List[int]) -> int:m = 0 # 或的最大值for n in nums:m |= ndef dfs(index,cur_sum):if index==len(nums) and cur_sum==m:return 1if index==len(nums) and cur_sum!=m:return 0#不选当前值a1=dfs(index+1,cur_sum)#选当前值a2=dfs(index+1,cur_sum|nums[index])return a1+a2return dfs(0,0)6023. 用地毯覆盖后的最少白色砖块
周赛t4，当时没时间做，被第二题卡着，哎。。
class Solution:def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:#在floor[i]==1的位置，放地毯或者不放地毯,#如果放地毯，遍历到i+carpetLen,如果不放地毯，遍历到i+1#后缀和，求从i到结尾的1的数量postsum=[0 for _ in range(len(floor))]if floor[-1]=="1":postsum[-1]=1for i in range(len(floor)-2,-1,-1):if floor[i]=="1":postsum[i]=postsum[i+1]+1else:postsum[i]=postsum[i+1]@lru_cache(None)def dfs(i,numCarpets):#如果没有地毯了，返回从i到结尾的1的数量if i>len(floor)-1:return 0# if numCarpets==0:# return postsum[i]a1,a2,a3=float("inf"),float("inf"),float("inf")if floor[i]=="1":a1=dfs(i+1,numCarpets)+1if numCarpets>=1:a2=dfs(i+carpetLen,numCarpets-1)if floor[i]=="0":a3=dfs(i+1,numCarpets)res=min(a1,a2,a3)return resreturn dfs(0,numCarpets)
2212. 射箭比赛中的最大得分
要是求最高分数的话是01背包，如下：
class Solution:def __init__(self):self.res=0def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:#01背包，在当前位置得分或者不得分，如果得分的话，当前位置比alice多1,统计最大值#当前位置得分，等价于，得到当前位置的indexres=[0 for _ in range(len(aliceArrows))]def dfs(i,numArrows,score):if i==len(aliceArrows):self.res=max(self.res,score)return 0#当前位置得分a1,a2=0,0if numArrows-aliceArrows[i]-1>=0:a1=dfs(i+1,numArrows-aliceArrows[i]-1,score+i) a2=dfs(i+1,numArrows,score)return max(a1,a2)res=dfs(0,numArrows,0)return self.resclass Solution:def __init__(self):self.res=0self.bobres=[]self.shengyu=0def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:#回溯，输出路径bob=[0 for _ in range(len(aliceArrows))]def dfs(i,numArrows,bob,score):if i==len(aliceArrows):if score>self.res:self.res=score# print(bob,score)self.bobres=bob[:]#如果还有多余的。最后对self.bobres做处理if numArrows>0:self.shengyu=numArrowsif numArrows==0:self.shengyu=0return for j in range(i,len(aliceArrows)):#当前位置选if numArrows-aliceArrows[j]-1>=0:#如果不是最后一个，aliceArrows[j]+1if j<len(aliceArrows)-1:bob[j]=aliceArrows[j]+1numArrows=numArrows-aliceArrows[j]-1dfs(j+1,numArrows,bob,score+j)bob[j]=0numArrows=numArrows+aliceArrows[j]+1else:#如果j是最后一个需要判断箭的数量是不是多余bob[j]=numArrowsnumArrows=0dfs(j+1,numArrows,bob,score+j)numArrows=bob[j]bob[j]=0else:#当前位置不选dfs(j+1,numArrows,bob,score)res=[]dfs(0,numArrows,bob,0)if self.shengyu>0:for i in range(len(aliceArrows)):if self.bobres[i]>0:self.bobres[i]+=self.shengyu breakreturn self.bobres5269. 从栈中取出 K 个硬币的最大面值和
01背包延伸
class Solution:def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:#01背包，从当前栈中取或者不取，从当前栈中连续取x个@lru_cache(None)def dfs(index,k):if k==0:return 0if index == len(piles):return 0res = 0#当前栈不取a1 = dfs(index+1,k)#当前栈取a2 = 0s=0for i in range(min(len(piles[index]),k)):s = s+piles[index][i]k = k-1a2 = max(a2,s + dfs(index+1,k))return max(a1,a2) return dfs(0,k)1230. 抛掷硬币
LeetCode-Python-1230. 抛掷硬币(数学 + DP）_暴躁老哥在线刷题的博客-CSDN博客
class Solution(object):def probabilityOfHeads(self, prob, target):""":type prob: List[float]:type target: int:rtype: float"""dp = [[0 for _ in range(len(prob) + 1)] for _ in range(len(prob))]# dp[i][j] 表示前i个硬币里，有j个硬币正面朝上的概率dp[0][1] = prob[0]dp[0][0] = 1 - prob[0]for i, p in enumerate(prob):for j in range(target + 1):if i > 0:dp[i][j] += dp[i - 1][j] * (1 - p) # 当前硬币正面朝下dp[i][j] += dp[i - 1][j - 1] * (p) # 当前硬币正面朝上return dp[-1][target]完全背包
322 零钱兑换
深搜
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:@lru_cache(None)def dfs(index,cur_sum):if cur_sum==amount:return 0if cur_sum>amount:return float("inf")res=float("inf")for i in range(index,len(coins)):# #不选i，就把index+1# a1=dfs(index+1,cur_sum)# #选ia2=dfs(index,cur_sum+coins[i])+1res=min(res,a2)# cur_ans=min(a1,a2)# res=min(res,cur_ans)return res res=dfs(0,0)if res==float("inf"):return -1return res
删除一些代码之后
这种写法不会造成重复搜索吗。比如index=2的时候，还会遍历到index=1,而index=1的时候，已经遍历过了。
这个 lru 装饰器已经保存了 之前计算过的 dfs 了，
这个cache就是 dp的memorization，lru是一种 cache策略
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:@lru_cache(None)def dfs(cur_sum):if cur_sum==amount:return 0res=float("inf")for i in range(len(coins)):#选iif cur_sum+coins[i]<=amount:a2=dfs(cur_sum+coins[i])+1res=min(res,a2)return res res=dfs(0)if res==float("inf"):return -1return res
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:#完全背包，每种硬币都是无限的。#dfs的参数是amount@lru_cache(None)def dfs(amount):if amount==0:return 0res=float('inf')for i in range(len(coins)):#选当前的iif amount-coins[i]>=0:a1=dfs(amount-coins[i])+1res=min(res,a1)return resb1=dfs(amount)if b1==float('inf'):return -1return b1动态规划
如下动态规划解法（dp[i]表示到i为止,使用的最小硬币。）行不通，因为遍历一次，只说明使用了一次。
class Solution(object):def coinChange(self, coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""#dp[i]表示到i为止,使用的最小硬币。#当coins[i] < amount的时候，可以使用coins[i]#遍历一次，只说明使用了一次for i in range(len(coins)):if coins[i] < amount:cur = dp[i-1] + 1dp[i] = min(dp[i],cur)return dp[-1]正确的思路是
class Solution(object):def coinChange(self, coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""dp = [float("inf") for _ in range(amount+1)]dp[0] = 0for i in range(len(coins)):for j in range(amount+1):if j >= coins[i]:dp[j] = min(dp[j],dp[j-coins[i]]+1)if dp[-1] == float("inf"):return -1return dp[-1]518 零钱兑换2
深搜
要加index，防止往回走。
class Solution:def change(self, amount: int, coins: List[int]) -> int:@lru_cache(None)def dfs(index,cur_sum):if cur_sum==amount:return 1if cur_sum>amount:return 0res=0for i in range(index,len(coins)):res+=dfs(i,cur_sum+coins[i])return resreturn dfs(0,0)class Solution:def change(self, amount: int, coins: List[int]) -> int:@lru_cache(None)def dfs(index,amount):if amount==0:return 1res=0for i in range(index,len(coins)):if amount-coins[i]>=0:a1=dfs(i,amount-coins[i])res+=a1return res return dfs(0,amount)动态规划
class Solution(object):def change(self, amount, coins):""":type amount: int:type coins: List[int]:rtype: int"""dp = [0 for _ in range(amount+1)]dp[0] = 1for i in range(len(coins)):for j in range(amount+1):if j >= coins[i]:dp[j] += dp[j-coins[i]]return dp[-1]139 单词拆分
开始的解法如下，有个错误的地方，代码里没有考虑到不选当前 可选 单词的情况。
解决办法：在循环的时候加上对res的 or,可以判断出以每个单词为开头的情况。
class Solution(object):def wordBreak(self, s, wordDict):""":type s: str:type wordDict: List[str]:rtype: bool"""#完全背包问题，每个单词可以用无限多次。#dfs里的循环是从0遍历wordDict,dfs的index是s的下标，表示从s[index]开始遍历def dfs(index):#如果s遍历到了最后if index == len(s):return Truefor i in range(len(wordDict)):cur = wordDict[i]#如果当前词可以匹配上,分为要和不要两种if s[index:index+len(cur)] == cur:return dfs(index+len(cur))#都遍历完了还没有true就return falsereturn Falsereturn dfs(0)正确的解法
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:#完全背包问题，每个单词可以用无限多次。#dfs里的循环是从0遍历wordDict,dfs的index是s的下标，表示从s[index]开始遍历@lru_cache(None)def dfs(index):#如果s遍历到了最后if index == len(s):return Trueres = Falsefor i in range(len(wordDict)):cur = wordDict[i]#如果当前词可以匹配上,分为要和不要两种if s[index:index+len(cur)] == cur:res = dfs(index+len(cur)) or res#都遍历完了还没有true就return falsereturn resreturn dfs(0)140.单词拆分2
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:#完全背包的回溯，输出路径path = []res = []def dfs(index):if index == len(s):res.append(" ".join(path))for i in range(len(wordDict)):cur = wordDict[i]if s[index:index+len(cur)] == cur:path.append(cur)dfs(index+len(cur))path.pop()dfs(0)return res1449. 数位成本和为目标值的最大数字
回溯:超时
class Solution:def __init__(self):self.size=0def largestNumber(self, cost: List[int], target: int) -> str:#cost[i]能组成target，完全背包，输出路径(回溯). 再找到最大的index组合def dfs(index,target):if target==0:if path not in res:if len(path)>=self.size:res.append(path[:])self.size=len(path)for i in range(index,-1,-1):if target-cost[i]>=0:path.append(i+1)dfs(i,target-cost[i])path.pop()path=[]res=[]dfs(len(cost)-1,target)#res里数字的index+1print(res)res2=[]for i in range(len(res)):tmp=[]for h in range(len(res[i])):tmp.append(str(res[i][h]))res2.append(int(''.join(tmp)))res2.sort(reverse=True)if len(res2)>0:return str(res2[0])return "0"
在递归的时候用value递归，递归完了之后记录index。可以不用回溯的方法把所有路径都输出
class Solution:def largest_number(self, cost: List[int], target: int) -> str:def compare(a: str, b: str) -> bool:return a > b if len(a) == len(b) else len(a) > len(b)@lru_cache(None)def dfs(x: int) -> str:if x == 0:return ''res = '0'for i in range(len(cost)):if cost[i] <= x:ret = dfs(x - cost[i])if ret != '0':ret = str(i + 1) + retif compare(ret, res):res = retreturn resreturn dfs(target)作者：eequalmcc
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class Solution:def largestNumber(self, cost: List[int], target: int) -> str:#完全背包#从后往前遍历，target-cost[i]==0的时候返回def compare(s1,s2):if len(s1)>len(s2):return True#res2是后面遍历的，即index在res前面if len(s1)<len(s2):return Falseif len(s1)==len(s2):return s1>s2@lru_cache(None)def dfs(target):if target==0:return ""res="0"for i in range(len(cost)-1,-1,-1):#选当前的cost[i]if target-cost[i]>=0:cur_res=dfs(target-cost[i])#要加这个判断，如果不符合条件就不返回if cur_res!="0":res2=str(i+1)+cur_res#如果res2比res大，设res为res2if compare(res2,res):res=res2return res a1=dfs(target)return a1
动态规划
class Solution:def largestNumber(self, cost: List[int], target: int) -> str:# 定义 dp[i][j] 表示 选择前 i 个数字, 总成本恰好等于 j 的 "最大整数"dp = ["0" for _ in range(target + 1)]dp[0] = ""def maxInt(a, b):if len(a) == len(b):return max(a, b)elif len(a) > len(b):return aelse:return bfor i in range(1, len(cost) + 1):# 只需要遍历 j >= cost[i-1] 的那部分for j in range(cost[i-1], target+1):if dp[j- cost[i-1]] != "0":dp[j] = maxInt(dp[j], str(i) + dp[j - cost[i-1]])return dp[-1]作者：niconiconi-12
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。2100. 适合打劫银行的日子
class Solution {public List<Integer> goodDaysToRobBank(int[] security, int time) {int n = security.length;// 用于记录当前下标下左侧的满足条件的天数的值int []leftDay = new int[n];// 用于记录当前下标右侧的满足条件的天数的值int []rightDay = new int[n];// 从左往右开始记录当前日子下标符合条件的左侧日子数量// 从右往左开始记录当前日子下标符合条件的右侧日子数量for (int i = 1 ;i < n;i++){if (security[i] <= security[i-1])leftDay[i] = leftDay[i-1] + 1;if (security[n- i - 1] <= security[n-i])rightDay[n- i - 1] = rightDay[n - i] + 1;}List<Integer> res = new ArrayList<>();// 从左往右遍历窗口中的日期 比较记录日期下表对应的左侧符合条件的左侧日子数量和符合条件的右侧日子数量即可for (int i = time;i< n -time;i++){if (leftDay[i] >= time && rightDay[i] >=time)res.add(i);}return res;}
}作者：alascanfu
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。二刷
#和最大子数组和，那个经典的动态规划是有点像的。用两个dp数组，一个从左往右，一个从右往左
#存储到当前为止满足条件的，如果不满足条件就从1开始，如果满足条件就累加
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:def goodDaysToRobBank(self, security, time):#dp_left[i]表示i-1和i,i-2和i-1的递增性dp_left = [0 for _ in range(len(security))]for i in range(1,len(security)):if security[i] <= security[i-1]:dp_left[i] = dp_left[i-1] + 1else:dp_left[i] = 0dp_right = [0 for _ in range(len(security))]for i in range(len(security)-2,-1,-1):if security[i] <= security[i+1]:dp_right[i] = dp_right[i+1] + 1else:dp_right[i] = 0res = []for i in range(len(security)):if dp_left[i] >= time and dp_right[i] >= time:res.append(i)return res691. 贴纸拼词
错误的回溯
maps存储target里的字母出现次数。这么写是错的，
if flag == True:
dfs(index,count+1)
#恢复maps
for i in range(len(cur)):
if cur[i] in maps:
maps[cur[i]] += 1
dfs(index+1,count)
else:
dfs(index + 1, count)
应该是没有搜到所有的状态。完全背包一般是在dfs里写for循环，这个写法哪里不对现放一下，重点理解一下一般情况下背包问题的解法。
class Solution:def minStickers(self, stickers: List[str], target: str) -> int:self.res = float("inf")from collections import Countermaps = Counter(target)def dfs(index,count):# print(count,maps)res_flag = Falsefor key in maps:if maps[key] > 0:res_flag = Truebreakif res_flag == False:self.res = min(self.res,count)returnif index > len(stickers)-1:returncur = stickers[index]flag = Falsefor i in range(len(cur)):if cur[i] in maps and maps[cur[i]] > 0:flag = Truemaps[cur[i]] -= 1if flag == True:dfs(index,count+1)#恢复mapsfor i in range(len(cur)):if cur[i] in maps:maps[cur[i]] += 1dfs(index+1,count)else:dfs(index + 1, count)dfs(0,0)if self.res == float("inf"):return -1return self.res正确的背包写法
LeetCode 贴纸拼词（回溯法+备忘录）_hestyle的博客-CSDN博客
class Solution:def minStickers(self, stickers: List[str], target: str) -> int:from collections import Counter@lru_cache(None)def dfs(index,cur_target):if cur_target == "":return 0res = float("inf")for i in range(index,len(stickers)):#选了i之后的cur_targetcur = stickers[i]cur_maps = Counter(cur)new_target = ""for h in range(len(cur_target)):if cur_target[h] in cur_maps and cur_maps[cur_target[h]] > 0:cur_maps[cur_target[h]] -= 1continueelse:new_target += cur_target[h]if new_target!= cur_target:res = min(res,dfs(i,new_target) + 1)return resres = dfs(0,target)if res == float("inf"):return -1return res完全背包+状态压缩
public int minStickers(String[] stickers, String target) {int n = target.length();//存储所有子序列所需的贴纸值int[] memory = new int[1 << n];Arrays.fill(memory, -1);//空序列不需要贴纸memory[0] = 0;//计算target对应的状态号的贴纸数量//我们可以把每个子序列都对应到一个mask(掩码，类比到网络的子网掩码)上，这里是一对一的关系//以“tar”为例：// 000 -> "" 100 -> "t"// 001 -> "r" 101 -> "tr"// 010 -> "a" 110 -> "ta"// 011 -> "ar" 111 -> "tar"int ans = dp(stickers, target, memory, (1 << n) - 1);//最多是n个贴纸，否则贴纸没有完全覆盖所有的字母，返回-1return ans <= n ? ans : -1;}/*** 返回mask对应的贴纸数量** @param stickers 贴纸* @param target 目标值* @param memory 有可能会重复计算 mask对应的贴纸* @param mask 子序列* @return*/private int dp(String[] stickers, String target, int[] memory, int mask) {int n = target.length();if (memory[mask] < 0) {int ans = n + 1;for (String sticker : stickers) {//剩余left个int left = mask;int[] chars = new int[26];//统计每个贴纸的 字母个数for (int i = 0; i < sticker.length(); i++) {chars[sticker.charAt(i) - 'a']++;}for (int i = 0; i < target.length(); i++) {char c = target.charAt(i);//判断mask是否有第i个字母 并且该贴纸是否有此字母if (((mask >> i) & 1) == 1 && chars[c - 'a'] > 0) {chars[c - 'a']--;//做异或处理//比如现在是i == 0 并且 111 -> "tar"；c == ‘r’//则剩余left ^= 1// 111// ^ 001// -------// = 110left ^= (1 << i);}}//left是剩下没有的字母if (left < mask) {// 计算left 再加上当前sticker（也就是+1）就是mask所需要的stickers// 即 f(mask) = f(left) + 1ans = Math.min(ans, dp(stickers, target, memory, left) + 1);}}memory[mask] = ans;}return memory[mask];}作者：jiang-hui-4
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class Solution:def minStickers(self, stickers: List[str], target: str) -> int:m = len(target)from collections import Counter@lru_cache(None)def dfs(mask):#当所有位置为0的时候，说明target全为0了if mask == 0:return 0res = m + 1for sticker in stickers:left = maskcnt = Counter(sticker)for i, c in enumerate(target):#如果mask的第i位是1if mask & (1 << i) and cnt[c]:cnt[c] -= 1#把mask的第i位设置为0left ^= 1 << iif left < mask:res = min(res, dfs(left) + 1)return res#比如m等于15,那这个就是把15位全设置为1res = dfs((1 << m) - 1)return res if res <= m else -1打家劫舍
198 打家劫舍
力扣
深搜
class Solution:def rob(self, nums: List[int]) -> int:#深搜，偷或者不偷，遍历每种情况@lru_cache(None)def dfs(i,flag):if i > len(nums)-1:return 0res = float("-inf")#上一家没有偷，这一家可以偷if flag == False:a1 = dfs(i+1,True) + nums[i]a2 = dfs(i+1,False)res = max(res,(max(a1,a2)))else:res = max(res,dfs(i+1,False))return resreturn dfs(0,False)动规
动规空间优化
213 打家劫舍2
深搜
class Solution:def rob(self, nums: List[int]) -> int:@lru_cache(None)def dfs(i,flag,first_flag):if i==1:#第一个值偷了if flag == True:first_flag = Trueelse:first_flag = False#最后一个值，如果最后一个的前一个没偷，而且nums[0]没偷，则最后一个值可偷if i==len(nums) - 1:if flag == False and first_flag == False:return nums[-1]else:return 0#前一个值没偷，那么当前的可偷，可不偷res = float("-inf")if flag == False:a1 = dfs(i+1,True,first_flag) + nums[i]a2 = dfs(i+1,False,first_flag)res = max(a1,a2)else:res = dfs(i+1,False,first_flag)return resreturn dfs(0,False,False)动态规划
class Solution:def rob(self, nums: List[int]) -> int:#用动态规划时，由于是环形数组，直接用正向方式的思考，情况比较多。#换一种方式，用脑筋急转弯的方式思考。没选数组的第一个数，没选数组的最后一个数。只有这两种情况。def get_dp(arr):dp = [0 for _ in range(len(arr))]dp[0] = arr[0]if len(arr) > 1:dp[1] = max(arr[0],arr[1])for i in range(2,len(arr)):dp[i] = max(dp[i-1],dp[i-2] + arr[i])return dp[-1]if len(nums) == 1:return nums[0]a1 = get_dp(nums[1:])a2 = get_dp(nums[:len(nums)-1])print(a1,a2)return max(a1,a2)337. 打家劫舍 III
深搜
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def rob(self, root: TreeNode) -> int:@lru_cache(None)def dfs(root,flag):a1,a2 = 0, 0a3,a4 = 0, 0res = float("-inf")if flag == False:if root.left:a1 = dfs(root.left,True)if root.right:a2 = dfs(root.right,True)res = max(res,a1 + a2 + root.val)if root.left:a3 = dfs(root.left,False)if root.right:a4 = dfs(root.right,False)res = max(res,a3 + a4)return resreturn dfs(root,False)爬楼梯问题
6058. 统计打字方案数
力扣
比如2222，最后一个2有3种可能的状态，它自己单独按，它和它的前一个按(连续按2下），它和它的前2个按(连续按3下）
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
class Solution {
public:int mod = 1e9 +7;int countTexts(string pressedKeys) {long long len = pressedKeys.length();vector<long long> dp(len + 1);dp[0] = 0;dp[1] = 1;char now = pressedKeys[0];long long cnt = 1;long long ans = 1;for(int i = 1;i<len;i++){if(pressedKeys[i] == now){cnt++;if(now == '7' || now == '9'){if(cnt == 2){dp[cnt] = (dp[cnt - 1] + dp[cnt - 2]) % mod;}else if(cnt == 3){dp[cnt] = (dp[cnt - 1] + dp[cnt - 2] + dp[cnt - 3]) % mod;}else {dp[cnt] = (dp[cnt-1] + dp[cnt-2] + dp[cnt-3] + dp[cnt-4]) % mod;}}else{if(cnt == 2){dp[cnt] = (dp[cnt - 1] + dp[cnt - 2]) % mod;}else {dp[cnt] = (dp[cnt - 1] + dp[cnt - 2] + dp[cnt - 3] + 1) % mod;}}}else{ans = (ans*dp[cnt])%mod;now = pressedKeys[i];cnt = 1;dp[0] = 0;dp[1] = 1;}}ans = (ans*dp[cnt])%mod;return ans;}
};6100. 统计放置房子的方式数
class Solution(object):def countHousePlacements(self, n):""":type n: int:rtype: int"""#要当前idp1 = [0 for _ in range(n)]#不要当前idp2 = [0 for _ in range(n)]dp1[0] = 1dp2[0] = 1if n > 1:dp1[1] = 1dp2[1] = 2for i in range(2,n):dp1[i] = dp2[i-1]dp2[i] = dp2[i-1] + dp1[i-1]# print(dp1)# print(dp2)return (dp1[-1]+dp2[-1])*(dp1[-1]+dp2[-1]) % (10**9+7)二刷
class Solution(object):def countHousePlacements(self, n):""":type n: int:rtype: int"""mod = 10 ** 9 + 7dp = [0 for _ in range(n+1)]dp[0] = 1dp[1] = 2for i in range(2,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[-1] * dp[-1] % mod6011. 完成比赛的最少时间
class Solution(object):def minimumFinishTime(self, tires, changeTime, numLaps):""":type tires: List[List[int]]:type changeTime: int:type numLaps: int:rtype: int"""#先求单个轮胎跑x圈的最小耗时，中间不换胎。#根据数据范围，最大值是15# 走一圈花费的最小时间min_time = [x[0] for x in tires]costx=[float("inf") for _ in range(1001)]for i in range(len(tires)):cur=tires[i]fi=cur[0]ri=cur[1]curtime=0x=1while fi*ri**(x-1)<=changeTime+min_time[i]:curtime+=fi*ri**(x-1)if curtime<costx[x]:costx[x]=curtimex+=1# print(costx)dp=[0 for _ in range(numLaps+1)]for i in range(1,numLaps+1):#中间不换胎dp[i]=costx[i]#在j处换胎。最后一个轮胎连续跑了j圈，爬楼梯的思想for j in range(1,i+1):dp[i]=min(dp[i],costx[j]+dp[i-j]+changeTime)print(dp)return dp[-1]873. 最长的斐波那契子序列的长度
两数之和
class Solution(object):def lenLongestFibSubseq(self, arr):""":type arr: List[int]:rtype: int"""#dp[i][j]表示以arr[i],arr[j]结尾的最长斐波那契式#k为i之前的一个数，dp[i][j] = max(dp[i][j],dp[k][i] + 1),arr[k] + arr[i] = arr[j]dp = [[0 for _ in range(len(arr))] for _ in range(len(arr))]maps = {}res = 0for j in range(len(arr)):for i in range(j-1,-1,-1):#枚举kneed = arr[j] - arr[i]if need in maps and maps[need] < i:need_index = maps[need]if dp[need_index][i] == 0:dp[i][j] = max(3,dp[i][j])else:dp[i][j] = max(dp[need_index][i] + 1,dp[i][j])res = max(res,dp[i][j])maps[arr[j]] = jreturn res路径dp
5270. 网格中的最小路径代价
狄杰斯特拉
class Solution:def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:from collections import dequeimport heapqgraph = collections.defaultdict(list)for i in range(len(grid)-1):cur = grid[i]nexts = grid[i+1]for j in range(len(cur)):graph[cur[j]]=nextsdef bfs():ans = float("inf")# deq.append(((start,cost),1))dist = collections.defaultdict(int)heap = []for i in range(len(grid[0])):start = grid[0][i]cost = startdist[start] = startheapq.heappush(heap, (cost,(start, 1)))while heap:cost,(node,d) = heapq.heappop(heap)next_nodes = graph[node]if d+1 <= len(grid):for h in range(len(next_nodes)):next_node = next_nodes[h]cost1 = moveCost[node][h]# heapq.heappush(((next_node,cost+next_node+cost1),d+1))if dist[next_node]>0 and cost+next_node+cost1 < dist[next_node]:heapq.heappush(heap, (cost+next_node+cost1,(next_node, d+1)))dist[next_node] = cost + next_node + cost1elif dist[next_node] == 0:heapq.heappush(heap, (cost + next_node + cost1, (next_node, d + 1)))dist[next_node] = cost + next_node + cost1else:continueelse:ans = costbreakreturn ans# res = float("inf")# for k in range(len(grid[0])):# tmp = bfs(grid[0][k])# res = min(res,tmp)return bfs()dp
class Solution {public int minPathCost(int[][] grid, int[][] moveCost) {int n = grid.length, m = grid[0].length;int[][] dp = new int[n][m];//dp[i][j]表示以gril[i][j]结尾的路径的最小值int ans = Integer.MAX_VALUE;for (int i = 0; i < dp.length; i++) {Arrays.fill(dp[i], Integer.MAX_VALUE);}for (int j = 0; j < m; j++) {dp[0][j] = grid[0][j];}for (int i = 1; i < n; i++) {for (int j = 0; j < m; j++) {for (int k = 0; k < m; k++) {/*** dp[i - 1][k] 从dp[i-1][k]到dp[i][j]* moveCost[grid[i - 1][k]][j] 从dp[i-1][k]到dp[i][j]的路径的值* grid[i][j] 该点的值*/dp[i][j] = Math.min(dp[i - 1][k] + moveCost[grid[i - 1][k]][j] + grid[i][j],dp[i][j]);}}}n--;//为了方便枚举终点的路径最小值for (int j = 0; j < m; j++) {ans = Math.min(ans, dp[n][j]);//寻找达到尾部的最小值}return ans;}
}作者：shou-hu-zhe-t
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。基础经典dp
整数拆分
hard经典dp
887. 鸡蛋掉落
class Solution:def superEggDrop(self, k: int, n: int) -> int:@lru_cache(None)def dfs(k,n):if k == 1:return nif n == 0:return 0res = float("inf")# for i in range(1,n+1):# #从第i层扔# #鸡蛋碎了:f一定在i下面# #鸡蛋没碎:f在i上面# res=min(res,max(dfs(k-1,i-1),dfs(k,n-i)) + 1)res = float('inf')low, high = 1, nwhile low <= high:mid = (low + high) // 2broken = dfs(k - 1, mid - 1) # 碎了的情况下，在最坏情况下还需要的最小尝试次数not_broken = dfs(k, n - mid) # 没碎的情况下，在最坏情况下还需要的最小尝试次数# res = min(max(碎，没碎) + 1) # 两种情况需要取最大值，作为最坏情况的最少尝试次数，+1代表本次尝试if broken > not_broken: # 如果碎了后的还需要尝试情况大于没有碎的还需尝试情况，说明high = mid - 1res = min(res, broken + 1)else:low = mid + 1res = min(res, not_broken + 1)return resreturn dfs(k,n)312. 戳气球
class Solution:def maxCoins(self, nums: List[int]) -> int:n = len(nums)nums = [1] + nums + [1]@functools.lru_cache(None)def dfs(left, right):if left >= right-1: # 递归终止条件：开区间 (left, right) 中没有元素return 0best = 0# k: 开区间 (left, right) 中最后一个被戳破的气球for k in range(left+1, right): # 枚举k# 在 i 之前，开区间 (left, i) 和 (i, right) 区间中的气球均已被戳破best = max(best, dfs(left, k) + nums[left]*nums[k]*nums[right] + dfs(k, right))return bestreturn dfs(0, n+1)作者：flix
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。188. 买卖股票的最佳时机 IV
更多推荐
背包问题/打家劫舍/股票问题/爬楼梯问题v2
发布评论