企业官网建设流程全解析

那个网站可以学做西餐,盘锦威旺做网站,seo是付费推广吗,怎么做网站图片1.0-1背包问题#xff1a;#capacity :背包容量#w[i]#xff1a;第i个物体的体积#v[i]#xff1a;第i个物体的价值def dfs(i , c): 定义#xff1a;选或不选到第i个物体时#xff0c;目前背包最大价值i:目前装了i个物体 c#xff1a;背包剩余容量回溯公式#xf…1.0-1背包问题#capacity :背包容量#w[i]第i个物体的体积#v[i]第i个物体的价值def dfs(i , c): 定义选或不选到第i个物体时目前背包最大价值i:目前装了i个物体 c背包剩余容量回溯公式dfsi,cmax(dfs(i-1,c),dfs(i-1,c-w[i])v[i]) 装没装第i个物体的两种情况边界条件1.i 0 没东西可装2. 剩余容量不足以装下当前的这个w[ i ]#capacity :背包容量 #w[i]第i个物体的体积 #v[i]第i个物体的价值 n len(w) def dfs(i,c): if i 0: return 0 if c w[i]: return dfs(i-1,c) return max(dfs(i-1,c),dfs(i-1,c-w[i])v[i]) dfs(n-1,capacity)1.1.目标和 问题1.回溯法cache目标和问题可以转换为0-1背包问题因为最后也是从数组中选出几个数使其最终和为一个定值令p正数和q负数和 sums p-q target pq可以得出 p sumtarget//2 即几个数和为定值dfsit定义从i个数中选出和为t的 方案个数参数i从包括i及其往前的数字中选t现在要凑的目标和回溯方程dfs(i,t) dfs(i-1,t) dfs(i-1,t-nums[i])边界条件若sumtarget并不是偶数或者为负数那就无解返回 0边界条件若当前的nums[i] t那就加不进去return dfs(i-1,t)初始条件if i 0: //没有可选的了从n已经遍历到开头了if t0:return 1 此方案可行else: return 0 没有恰好为t的方案代码时间复杂度t*n空间复杂度n时间复杂度你可以把这个dfs函数的执行过程理解成 “填一张 n 行、t 列的表格”class Solution: def findTargetSumWays(self, nums: List[int], target: int) - int: target sum(nums)target n len(nums) if target%2 ! 0 or target0: return 0 t target//2 cache def dfs(i,t): if i0: if t0: return 1 else: return 0 if nums[i]t: return dfs(i-1,t) return dfs(i-1,t) dfs(i-1,t-nums[i]) return dfs(n-1,t)2.递推先根据回溯公式写出f公式dfs(i,t) dfs(i-1,t) dfs(i-1,t-nums[i])f[i][t] f[i-1][t] f[i-1][t-nums[i]]数组最好不要出现负数情况f [ i 1 ] [ t ] f [ i ] [ t ] f [ i ] [ t - nums[ i ] ]于是自然想到建立一个f[[]]二维数组 为了边界条件我们的二维数组会多一列、一行公式f [ [0] *(t 1) for _ in range(n1) ] *的是列数量 for的是行数量n1对于前0个1个...n个元素t 对应 凑出和为0 1 ...t的数递归变循环怎么变取决于f公式需要什么f [ i 1 ] [ t ] f [ i ] [ t ] f [ i ] [ t - nums[ i ] ] 可以看出需要 i t , nums[ i ]for i,x in enumerate(nums):for c in range(t1):边界条件nums[i]t: 在这就是 xc时间复杂度t n 空间复杂度 t nclass Solution: def findTargetSumWays(self, nums: List[int], target: int) - int: target sum(nums)target n len(nums) if target%2 ! 0 or target0: return 0 t target//2 f [[0]*(t1)for _ in range(n1)] f[0][0]1 for i,x in enumerate(nums): for c in range(t1): if xc: f[i1][c] f[i][c] else: f[i1][c] f[i][c]f[i][c-x] return f[n][t]3.空间优化两个数组发现f[i1]只取决于f[i]所以只需要两个数字之后的数组重新覆盖f0和f1即可f [[0]*(t1)for _ in range(2)] 两行数组f[i1]都改成f[(i1)%2]f[i]都改成f[i%2]空间复杂度为 t4.空间优化一个数组和i有关的都删掉遍历target的时候倒着遍历从t遍历至x倒序到 x只处理 c≥x 的场景避免重复选最开始的边界条件时间复杂度 tn 空间复杂度tclass Solution: def findTargetSumWays(self, nums: List[int], target: int) - int: target sum(nums)target n len(nums) if target%2 ! 0 or target0: return 0 t target//2 f [0]*(t1) f[0]1 for x in nums: for c in range(t,x-1,-1): f[c] f[c]f[c-x] return f[t]2.完全背包每个物品可以重复选回溯公式修改dfsi,cmax(dfs(i-1,c),dfs(i-1, c-w[i])v[i])dfs (i,c) min(dfs(i-1,c),dfs(i, c-w[i])v[i])选了但还可以选所以i不变2.1 零钱兑换1.回溯法cachedfs(i,c)定义用前i种硬币凑c块钱最少用几个硬币i前i种硬币c:还需要凑c块钱回溯方程dfs(i,c) min(dfs(i-1,c) dfs(i-,c-coins[i])1)边界条件1.若 coins[i]creturn dfs(i-1,c) 这类硬币滚蛋2.若i 0 andc!0说明还没凑完return inf 无解起始条件若 i0 and c0,return 0所有硬币都处理完了且剩余要凑的金额是 0不需要再用任何硬币i 0且c 0→ 返回 0含义所有硬币都处理完了且剩余要凑的金额是 0已经凑够了为什么返回 0因为 “没有硬币可选” 的情况下凑够了金额 0不需要再用任何硬币→ 最少硬币数就是 0举例子比如你要凑金额 0不管有没有硬币都只需要 0 个硬币啥都不用选这是所有最值问题的 “基础锚点”。class Solution: def coinChange(self, coins: List[int], amount: int) - int: n len(coins) cache def dfs(i,c): if i0: if c0:return 0 else: return inf if coins[i] c: return dfs(i-1,c) return min(dfs(i-1,c),dfs(i,c-coins[i])1) ans dfs(n-1,amount) if ans inf: return ans else: return -1