《labuladong的算法小超》A和《代码随想录》B阅读笔记(2)

2023年8月1日发(作者：)

《labuladong的算法⼩超》A和《代码随想录》B阅读笔记（2）第9天63.不同路径你看，今天就涉及到带有路障的机器⼈运动问题了。先上代码再解析class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: # 构造⼀个DP table row = len(obstacleGrid) col = len(obstacleGrid[0]) dp = [[0 for _ in range(col)] for _ in range(row)] dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0 if dp[0][0] == 0: return 0 # 如果第⼀个格⼦就是障碍，return 0 # 第⼀⾏初始化 for i in range(1, col): if obstacleGrid[0][i] != 1: dp[0][i] = dp[0][i-1] # 第⼀列初始化 for i in range(1, row): if obstacleGrid[i][0] != 1: dp[i][0] = dp[i-1][0] # 迭代过程 for i in range(1, row): for j in range(1, col): if obstacleGrid[i][j] != 1: dp[i][j] = dp[i-1][j] + dp[i][j-1] #return dp[-1][-1] 也可 return dp[row-1][col-1]在叙述的时候注意区分：输⼊数组的障碍物是1，⽽初始化的dp数组遇到障碍物处初始化为0.⾸先是解决“如果有障碍该怎么办”，当然是对应的dp保持为0确认动态规划的⼏个步骤：dp数组的含义与上道题相同递推公式相同，但因为加⼊了障碍，所以要多⼀步判断，判断不是障碍物之后再进⾏递推初始化相同，但要注意如果在⾏边界和列边界初始化是遇到障碍，则障碍物处保持为0，且障碍物之后的位置都是⽆意义的，因为不可能会遍历到那些位置，因此初始化为什么都可以。遍历顺序相同返回时返回最右下⾓位置。可以选择使⽤[-1][-1]和[m-1][n-1]两种形式。343.整数拆分哇哇哇，这道题可了不得，代码量很少，却是集动态规划的⼤成了可以说class Solution: def integerBreak(self, n: int) -> int: dp = [0] * (n + 1) dp[2] = 1 for i in range(3, n + 1): # 假设对正整数 i 拆分出的第⼀个正整数是 j（1 <= j < i），则有以下两种⽅案： # 1) 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * (i-j) # 2) 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[i-j] for j in range(1, i - 1): dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])) return dp[n]重点就在于注释中提到的：# 假设对正整数 i 拆分出的第⼀个正整数是 j（1 <= j < i），则有以下两种⽅案：# 1) 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * (i-j)# 2) 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[i-j]96.不同的⼆叉搜索树⼆叉搜索树是⼀个有序树：若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；它的左、右⼦树也分别为⼆叉搜索树class Solution: def numTrees(self, n: int) -> int: dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): for j in range(1, i + 1): dp[i] += dp[j - 1] * dp[i - j] return dp[-1]说实话，后⾯的这两道题没什么意思，有时间不如就直接背下来算了，我们还是看点有意思的动态规划：背包问题背包问题分类对于⾯试的话，其实掌握01背包，和完全背包，就够⽤了，最多可以再来⼀个多重背包。⾄于背包九讲其其他背包，⾯试⼏乎不会问，都是竞赛 级别的了，leetcode上连多重背包的题⽬都没有，所以题库也告诉我们，01背包和完全背包就够⽤了。⽽完全背包⼜是也是01背包稍作变化⽽来，即：完全背包的物品数量是⽆限的。所以背包问题的理论基础重中之重是01背包，所以⼀定要理解透。⼆维数组解决01背包问题1.确定dp数组以及下标的含义：dp[i][j] 表⽰从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少。2.确定递推公式：回顾⼀下dp[i][j]的含义：从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少。那么可以有两个⽅向推出来dp[i][j]，不放物品i：由dp[i - 1][j]推出，即背包容量为j，⾥⾯不放物品i的最⼤价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量⼤于背包j的重量时，物品i⽆法放进背包中，所以被背包内的价值依然和前⾯相同。)放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最⼤价值，那么dp[i - 1][j -weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最⼤价值。所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);注意dp[i][j]表⽰的是价值3.初始化：⾸先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，⽆论是选取哪些物品，背包价值总和⼀定为0。状态转移⽅程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就⼀定要初始化。dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最⼤价值。那么很明显当 j < weight[0]的时候，dp[0][j]应该是 0，因为背包容量⽐编号0的物品重量还⼩。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放⾜够放编号0物品。即i⽅向初始化为0，j⽅向初始化为最⼩价值，其余位置可初始化为任意值。4.遍历顺序：先遍历物品后遍历背包和先遍历背包后遍历物品没什么区别。虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上⾓，根本不影响dp[i][j]公式的推导！但先遍历物品再遍历背包这个顺序更好理解。第10天复习⼆维数组解决背包问题def test_2_wei_bag_problem1(bag_size, weight, value) -> int:

rows, cols = len(weight), bag_size + 1 dp = [[0 for _ in range(cols)] for _ in range(rows)]

# 初始化dp数组.

for i in range(rows):

dp[i][0] = 0 first_item_weight, first_item_value = weight[0], value[0] for j in range(1, cols):

if first_item_weight <= j:

dp[0][j] = first_item_value # 更新dp数组: 先遍历物品, 再遍历背包.

for i in range(1, len(weight)):

cur_weight, cur_val = weight[i], value[i] for j in range(1, cols):

if cur_weight > j: # 说明背包装不下当前物品.

dp[i][j] = dp[i - 1][j] # 所以不装当前物品.

else:

# 定义dp数组: dp[i][j] 前i个物品⾥，放进容量为j的背包，价值总和最⼤是多少。 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight]+ cur_val) print(dp)if __name__ == "__main__":

bag_size = 4 weight = [1, 3, 4] value = [15, 20, 30] test_2_wei_bag_problem1(bag_size, weight, value)背包问题：⼀维数组解决使⽤的是滚动数组，可以理解为⼆维数组的状态压缩，但我觉得理解起来倒是不难，可以这样理解：在使⽤⼆维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。其实可以发现如果把dp[i - 1]那⼀层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])。与其把dp[i - 1]这⼀层拷贝到dp[i]上，不如只⽤⼀个⼀维数组了，只⽤dp[j]（⼀维数组，也可以理解是⼀个滚动数组）。这是抽象的理解，其实从dp数组的含义上理解也可以。1.确定dp数组的定义：在⼀维dp数组中，dp[j]表⽰：容量为j的背包，所背的物品价值可以最⼤为dp[j]。2.递推公式：dp[j]为容量为j的背包所背的最⼤价值，dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表⽰容量为j - weight[i]的背包所背的最⼤价值。dp[j - weight[i]] + value[i] 表⽰ 容量为 j - 物品i重量的背包加上物品i的价值。（也就是容量为j的背包，放⼊物品i了之后的价值即：dp[j]）此时dp[j]有两个选择，⼀个是取⾃⼰dp[j] 相当于⼆维dp数组中的dp[i-1][j]，即不放物品i，⼀个是取dp[j -weight[i]] + value[i]，即放物品i，指定是取最⼤的，毕竟是求最⼤价值，所以递归公式为：dp[j] = max(dp[j], dp[j - weight[i]] +value[i]);可以看出相对于⼆维dp数组的写法，就是把dp[i][j]中i的维度去掉了。数组的初始化：dp[j]表⽰容量为j的背包，所背的物品价值可以最⼤为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最⼤价值就是0。因为dp数组在推导的时候⼀定是取价值最⼤的数，如果题⽬给的价值都是正整数，那么其余位置就都初始化为0就可以了。这样才能让dp数组在递归的过程中始终去最⼤的值，⽽不是被初始值覆盖了。数组的遍历顺序：⼆维dp遍历的时候，背包容量是从⼩到⼤，⽽⼀维dp遍历的时候，背包是从⼤到⼩。为什么呢？倒序遍历是为了保证物品i只被放⼊⼀次！。但如果⼀旦正序遍历了，那么物品0就会被重复加⼊多次！举⼀个例⼦：物品0的重量weight[0] = 1，价值value[0] = 15，如果正序遍历for(int i = 0; i < (); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); }}dp[1] = dp[1 - weight[0]] + value[0] = 15dp[2] = dp[2 - weight[0]] + value[0] = 30此时dp[2]就已经是30了，意味着物品0，被放⼊了两次，所以不能正序遍历。这是由于先遍历物品然后遍历背包容量⽽固定造成的。代码⽰范def test_1_wei_bag_problem(): weight = [1, 3, 4] value = [15, 20, 30] bag_weight = 4 # 初始化: 全为0 dp = [0] * (bag_weight + 1) # 先遍历物品, 再遍历背包容量 for i in range(len(weight)): for j in range(bag_weight, weight[i] - 1, -1): # 递归公式 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) print(dp)test_1_wei_bag_problem()dp数组的⼤⼩设定为bag_weight是因为包括了背包容量为0的情况其中第⼆层for循环中的右边界就只是weight[i]才对，但因为python的特性是左闭右开的，所以要减1递推公式可以理解为：背包现在状态下的价值和加⼊这个物品后的价值哪个更⼤。细节1是如果该物品的质量⼤于背包剩余质量，是不进⼊循环的。细节2是加⼊物品后要对应的和减去该物品质量后的那个背包状态下的价值去⽐较。第11天416.分割等和⼦集这道题主要体会问题转化为背包问题的思路，可以这样理解：背包质量为sum/2的情况下，最⼤(重量)能装下的物品的价值是否与sum/2相等。换句话说，只要你能在dp[-1]出找到值等于sum/2的情况，那么选取元素之外的剩余元素的和⼀定也是sum/2。dp[i]的数值⼀定是⼩于等于i的。如果dp[i] == i 说明，集合中的⼦集总和正好可以凑成总和i，理解这⼀点很重要。数组含义：dp[j]表⽰容量为j的背包，所背的物品价值可以最⼤为dp[j]。2.递推公式：dp[j] = max( dp[j], dp[j - weight[i]] + value[i] )这么看，这与01背包的唯⼀差别只是在返回值，代码⽰例：class Solution: def canPartition(self, nums: List[int]) -> bool: ji = nums

target = sum(ji) if target%2 != 0:return False

total_bag = target // 2 #print(total_bag)

dp = [0] * (total_bag+1 )

for i in range(len(ji)):

for j in range(total_bag, ji[i]-1,-1): dp[j] = max( dp[j], dp[j - ji[i]]+ji[i] ) return dp[total_bag] == total_bag

3.初始化：从dp[j]的定义来看，⾸先dp[0]⼀定是0。如果如果题⽬给的价值都是正整数那么⾮0下标都初始化为0就可以了，如果题⽬给的价值有负数，那么⾮0下标就要初始化为负⽆穷。这样才能让dp数组在递归公式的过程中取的最⼤的价值，⽽不是被初始值覆盖了。本题题⽬中 只包含正整数的⾮空数组，所以⾮0下标的元素初始化为0就可以了。4.遍历顺序：仍然是先遍历物品，然后遍历背包。1049.最后⼀块⽯头的重量II就这道题吧，让我想基本是想不出来的，看了题解后转化为416.分割等和⼦集问题后我能看得明⽩基本过程与上道题的思路⼏乎⼀样，唯⼀的差别在return处，我们详细的了解下本题其实就是尽量让⽯头分成重量相同的两堆，相撞之后剩下的⽯头最⼩，这样就化解成01背包问题了。最后dp[target]⾥是容量为target的背包所能背的最⼤重量。那么分成两堆⽯头，⼀堆⽯头的总重量是dp[target]，另⼀堆就是sum -dp[target]。在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] ⼀定是⼤于等于dp[target]的。那么相撞之后剩下的最⼩⽯头重量就是 (sum - dp[target]) - dp[target]。class Solution: def lastStoneWeightII(self, stones: List[int]) -> int: sum_tmp = sum(stones) #if sum_tmp%2 != 0: # return False half_sum = sum_tmp // 2 dp = [0] * (half_sum+1) for i in range(len(stones)): for j in range(half_sum, stones[i]-1, -1): dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]) return sum_tmp - 2*dp[half_sum]494.⽬标和这道题也可以说是神分析了本题要如何使表达式结果为target，既然为target，那么就⼀定有 left组合 - right组合 = target。left + right等于sum，⽽sum是固定的。公式来了， left - (sum - left) = target -> left = (target + sum)/2 。target是固定的，sum是固定的，left就可以求出来。此时问题就是在集合nums中找出和为left的组合。竟然就转化为了和上⾯两道题相同的思路先放代码class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: sumValue = sum(nums) if target > sumValue or (sumValue + target) % 2 == 1: return 0 bagSize = (sumValue + target) // 2 if bagSize <0: return 0 dp = [0] * (bagSize + 1) dp[0] = 1 for i in range(len(nums)): for j in range(bagSize, nums[i] - 1, -1): dp[j] += dp[j - nums[i]] return dp[bagSize]dp数组的含义：dp[j]表⽰填满 j 这么⼤容积的包，有 dp[j] 种⽅法确定递推公式：填满容量为j - nums[i]的背包，有dp[j - nums[i]]种⽅法。那么只要搞到nums[i]的话，凑成dp[j]就有dp[j - nums[i]] 种⽅法。举⼀个例⼦,nums[i] = 2： dp[3]，填满背包容量为3的话，有dp[3]种⽅法。那么只需要搞到⼀个2（nums[i]），有dp[3]⽅法可以凑齐容量为3的背包，相应的就有多少种⽅法可以凑齐容量为5的背包。那么需要把 这些⽅法累加起来就可以了，dp[j] += dp[j -nums[i]]

dp[j] += dp[j - nums[i]] ，这是⾸次接触到不同的递推公式，要注意递推公式的具体含义，每道题都要捋顺⼀下递推公式。在这道题中式计算⽅法的总和，所以⼀定是得到的⽅法相加。如果求解最⼩的那种⽅法就是之前的递推公式。初始化：dp[0] = 1，其余初始化为0遍历顺序：同上第12天474.⼀和零倒像是⼀道脑筋急转弯还是要锻炼那个能⼒，直接将dp数组抽象为题⽬中描述的结果，然后去思考怎么递推、怎么初始化、怎么遍历。dp数组含义：最多有i个0和j和1的strs的最⼤⼦集的⼤⼩是dp[i][j]递推公式：判断dp[i][j]与dp[i - zeroNum][j - oneNum]+1⼤⼩，即dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum]+1)初始化为0仍然是遍历物品再遍历背包class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: dp = [[0] * (n + 1) for _ in range(m + 1)] # 默认初始化0 # 遍历物品 for str in strs: ones = ('1') zeros = ('0') # 遍历背包容量且从后向前遍历！ for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1) return dp[m][n]完全背包理论01背包和完全背包唯⼀不同就是体现在遍历顺序上，所以我们可以直接针对遍历顺序经⾏分析！⾸先在回顾⼀下01背包的核⼼代码for(int i = 0; i < (); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); }}我们知道01背包内嵌的循环是从⼤到⼩遍历，为了保证每个物品仅被添加⼀次。⽽完全背包的物品是可以添加多次的，所以要从⼩到⼤去遍历，即// 先遍历物品，再遍历背包for(int i = 0; i < (); i++) { // 遍历物品 for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); }}再次基础上还要注意⼀下for循环的前后顺序，完全背包问题⼀般情况下这个顺序是不影响什么的，但根据题意还是要具体分析19.零钱兑换IIclass Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1

for i in range(len(coins)): for j in range(coins[i], amount+1): dp[j] += dp[j-coins[i]] return dp[-1]dp数组的含义：背包容量为j时凑成总⾦额的硬币组合数为dp[j]递推公式：dp[j] += dp[ j - coins[i] ]初始化：j=0时的硬币凑成⽅式只有⼀种(不进⾏凑硬币这项活动)，其余初始化为0遍历顺序：先遍历物品(从0到len(coins)的所有)，然后遍历价值(重量)，从coins[i]到最⼤的amount,由于python语⾔的特性，所以需要+1。⾃⼰⼼⾥推导⼀遍dp数组递推过程：⽆误第⼗三天377.组合总和IV组合总和的I、II、III，都是使⽤回溯算法求解的，⽽这道IV是以动态规划⽅式求解的，究其原因是因为这⾥需要求解组合数，⼀定意义上这也是⼀种求极值的形式(求最⼤能组合成多少种组合)，所以可以使⽤动态规划求解。此外，题⽬要求中“元素相同但顺序不同也被视为不同组合”，那么其实就是在求排列。数组的含义：选取凑成 j 时的组合数有dp[ j ]种2.递推公式：dp[j] = dp[j - nums[i]]3.初始化：求装满背包⼀共有多少种⽅法，应该是dp = [ 0 ] * (target + 1) ; dp[ 0 ] = 1;

4.遍历顺序：个数不限使⽤，说明是⼀个完全背包。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。如果把遍历nums(物品)放在外循环，遍历target作为内循环的话，举⼀个例⼦：计算dp[4]的时候，结果集只有[1, 3]这样的组合，不会有[3, 1]这样的组合，因为nums遍历在外层，3只出现在1的后⾯。

所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。5.举例dp数组的推导过程class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: dp = [0] * (target+1) dp[0] = 1 for i in range(1, target+1): for j in nums: if i>=j: dp[i] += dp[i-j] return dp[-1]注意先遍历背包再遍历物品的时候要多⼀步if i >= j的判断。

背包问题⼩结dp数组的含义：通常直奔主题；多数采⽤⼀维数组，少数使⽤⼆维数组。递推公式：求解最⼩值时⼤概率使⽤dp[ j ] = max( dp[j], dp[ j ][ j - wights[i] ] + value[i] )或者dp[ j ] = max( dp[j], dp[ j ][ j -wights[i] ] + 1 )；求解组合个数通常使⽤dp[j] = dp[j - nums[i]]。初始化：机器⼈问题初始化是先初始化⾸⾏，再初始化⾸列，其余元素初始化为0；计算个数时⾸元素初始化为1，其余元素初始化为0。遍历顺序：基本都是先遍历物品再遍历背包，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。。此外如果是01背包，则两道for循环是倒序遍历。如果是完全背包，则两道for循环是顺序遍历。70.爬楼梯今天我们使⽤动态规划写⼀下爬楼梯这道题的改进版：你可以⼀步⼀个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的⽅法可以爬到楼顶呢？学完动态规划，呀！我看看这是谁啊，这不是求组合数(多少种⽅法爬到楼顶)吗，这不正是⼀个状态转移的问题吗。仔细想⼀下可以发现，这和上⼀道题就是⼀摸⼀样的了。class Solution: def climbStairs(self, n: int) -> int: dp = [0]*(n + 1) dp[0] = 1 m = 2 # 遍历背包 for j in range(n + 1): # 遍历物品 for step in range(1, m + 1): if j >= step: dp[j] += dp[j - step] return dp[n]第14天322.零钱兑换这道题可以⽤来⽤来检验到⽬前为⽌动规算法的掌握程度，可以根据上⾯的背包问题⼩结试试写代码。dp数组的含义：凑成总⾦额为 j 需要硬币最少dp[j]个。根据dp数组含义，递推公式应为：dp [j] = max(dp[j], dp[j-coins[i]] +1)初始化：dp⼤⼩应amount + 1，dp[0]=1，因为凑成总额为0的硬币个数⼀定为0个，其余初始化为⽆穷⼤，因为递推过程中不能⼀定要覆盖初始化。遍历顺序：因为是可重复使⽤，所以是完全背包，则两层for循环是正向的。求得是组合数⽽不是排序数，则先遍历物品。举例递归：如果⼼算觉得不太清晰，不如就直接写代码输出dp观察结果。写代码：会发现写得很顺畅class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('INF')] * (amount+1) dp[0] = 0 for i in range(len(coins)): for j in range(coins[i], amount+1): dp[j] = min(dp[j-coins[i]]+1, dp[j]) if dp[amount]==float('INF'): return -1 return dp[amount]279.完全平⽅数可能刚看这种题感觉没啥思路，⼜平⽅和的，⼜最⼩数的。把题⽬翻译⼀下：完全平⽅数就是物品（可以⽆限件使⽤），凑个正整数n就是背包，问凑满这个背包最少有多少物品？感受出来了没，这么浓厚的完全背包氛围，和上⼀道题就是⼀样⼀样的！动规五部曲分析如下：确定dp数组（dp table）以及下标的含义：dp[j]：和为j的完全平⽅数的最少数量为dp[j]确定递推公式：dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。此时我们要选择最⼩的dp[j]，所以递推公式：dp[j] =min(dp[j - i * i] + 1, dp[j]);dp数组如何初始化：dp[0]表⽰ 和为0的完全平⽅数的最⼩数量，那么dp[0]⼀定是0。那0 * 0 也算是⼀种啊，为啥dp[0] 就是 0呢？看题⽬描述，找到若⼲个完全平⽅数（⽐如 1, 4, 9, 16, ...），题⽬描述中可没说要从0开始，dp[0]=0完全是为了递推公式。⾮0下标的dp[j]应该是多少呢？从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最⼩的，所以⾮0下标的dp[j]⼀定要初始为最⼤值，这样dp[j]在递推的时候才不会被初始值覆盖。确定遍历顺序：我们知道这是完全背包，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。本题也是⼀样的，是求最⼩数。所以本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！class Solution: def numSquares(self, n: int) -> int: nums = [i**2 for i in range(1, n+1) if i**2 <=n] dp = [float('INF')] * (n+1) dp[0] = 0 for num in nums: for j in range(num, n+1): dp[j] = min(dp[j], dp[j-num]+1) return dp[n]139.单词拆分和之前做过的回溯算法：分割回⽂串⽐较类似。在思考是不是回溯和动规的区别就是回溯是输出所有的情况的具体表现，⽽动规是输出最⼤最⼩的那种情况或者是情况的总数。确定dp数组以及下标的含义：dp[i] : 字符串长度为i的话，dp[i]为true，表⽰可以拆分为⼀个或多个在字典中出现的单词。确定递推公式：如果确定dp[j] 是true，且 [j, i] 这个区间的⼦串出现在字典⾥，那么dp[i]⼀定是true。（j < i ）。所以递推公式是 if([j, i]这个区间的⼦串出现在字典⾥ && dp[j]是true) 那么 dp[i] = true。dp数组如何初始化：从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]⼀定要为true，否则递归下去后⾯都都是false了。那么dp[0]有没有意义呢？dp[0]表⽰如果字符串为空的话，说明出现在字典⾥。但题⽬中说了“给定⼀个⾮空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。下标⾮0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为⼀个或多个在字典中出现的单词。确定遍历顺序：题⽬中说是拆分为⼀个或多个在字典中出现的单词，所以这是完全背包。还要讨论两层for循环的前后循序。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。本题最终要求的是是否都出现过，所以对出现单词集合⾥的元素是组合还是排列，并不在意！那么本题使⽤求排列的⽅式，还是求组合的⽅式都可以。即：外层for循环遍历物品，内层for遍历背包 或者 外层for遍历背包，内层for循环遍历物品 都是可以的。但本题还有特殊性，因为是要求⼦串，最好是遍历背包放在外循环，将遍历物品放在内循环。如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的⼦串都预先放在⼀个容器⾥。（如果不理解的话，可以⾃⼰尝试这么写⼀写就理解了）所以最终我选择的遍历顺序为：遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。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)]第15天704.⼆分查找以这道题为例，讲⼀下⼆分查找的两种代码思路第⼀种写法定义 target 是在⼀个在左闭右闭的区间⾥，也就是[left, right] （这个很重要⾮常重要）。区间的定义这就决定了⼆分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：while (left <= right) 要使⽤ <= ，因为left == right是有意义的，所以使⽤ <=if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]⼀定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1例如在数组：1,2,3,4,7,9,10中查找元素2，如图所⽰：代码及详细的注释：class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums)-1 ##定义target左闭右闭[left, right]的区间内，所以要注意-1 while(left <= right): ##当left==right，区间[left, right]仍然有效 mid = (left + right) // 2 ##取中间值 if nums[mid] > target: ##target在左区间， right = mid - 1 ##所以右边界mid-1 elif nums[mid] < target: ##target在右区间 left = mid + 1 ##所以左边界mid+1 else: ##如果left==right return mid ##则找到了结果 return -1 ##如果遍历之后仍没有找到则返回-1 第⼆种写法如果说定义 target 是在⼀个在左闭右开的区间⾥，也就是[left, right) ，那么⼆分法的边界处理⽅式则截然不同。有如下两点：while (left < right)，这⾥使⽤ < ,因为left == right在区间[left, right)是没有意义的if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，⽽寻找区间是左闭右开区间，所以right更新为middle，即：下⼀个查询区间不会去⽐较nums[middle]在数组：1,2,3,4,7,9,10中查找元素2，如图所⽰：（注意和⽅法⼀的区别）class Solution: def search(self, nums: List[int], target: int) -> int: # 第⼆种写法 left = 0 right = len(nums) ##定义target左闭右开[left, right)的区间内，所以没有-1 while(left < right): ##当left==right，区间[left, right)⽆效，所以没有= mid = (left + right) // 2 ##取中间值 if nums[mid] > target: ##target在左区间， right = mid ##所以右边界mid elif nums[mid] < target: ##target在右区间 left = mid+1 ##所以左边界mid+1 else: ##如果left==right return mid ##则找到了结果 return -1 ##如果遍历之后仍没有找到则返回-(x)本题的题意是：设计⼀个算法求解x的平⽅根可以转化为0-x列举，看看那个数字的平⽅与x⽐较接近class Solution: def mySqrt(self, x: int) -> int: l, r, ans = 0, x, -1 while l <= r: mid = (l + r) // 2 if mid * mid <= x: ans = mid l = mid + 1 else: r = mid - 1 return ans⼤体上遵循上⾯提到的顺序但由于这道题中有可能不会正好取到⼀个整数解⽽是⼀个近似整数解所以我们要把ans放置在⼀个if判断中class Solution: def isPerfectSquare(self, num: int) -> bool: left = 0 right = num while(left<=right): mid = (left + right) //2 if mid * mid == num: return True elif mid * mid < num: left = mid + 1 else: right = mid - 1 return False和上⾯的那道题⼏乎⼀模⼀样，不过由于这次是判断是否为完全平⽅数，因此是有==的情况的，没有的话就直接返回False了。第16天27.移除元素⾸先展⽰下我想到的⼀个特别快的⽅法，哈哈class Solution: def removeElement(self, nums: List[int], val: int) -> int: while (val in nums): (val) return len(nums)快慢指针 def removeElement(self, nums: List[int], val: int) -> int: # 快慢指针法 fast = low = 0 while fast < len(nums): if nums[fast] != val: nums[slow] = nums[fast] slow += 1 # 当fast指针遇到要删除的元素时停⽌赋值 # slow指针停⽌移动，fase指针继续前进 fast += 1 retuen slow从这道题开始，要接触双指针中的快慢指针了。快慢指针，顾名思义就是使⽤相对较快和相对较慢的两个指针在数组上进⾏操作，可在原数组上进⾏遍历⽽不需要开辟额外的空间。需要注意的是：low指针和fast指针的初始位置、if中fast指针的运算和if中元素如何交换这三处在本题中：因为要验证nums数组中和val相等的元素，所以low和fast都初始化为0快慢指针的循环边界⼀般由fast与len(x)来判断fast指针是与val判断相等if语句中要slow和fast处元素交换26.删除有序数组中的重复元素class Solution: def removeDuplicates(self, nums: List[int]) -> int: if not nums: return 0 n = len(nums) fast = 1 low = 0 while fast < n: if nums[fast] != nums[low]: nums[low + 1] = nums[fast] low += 1 fast += 1 return low + 1因为是验证本体数组内元素相等，所以low和fast指针不能相等，⾃然地，fast快了⼀步if中由fast处元素和low处元素⽐较因为重复元素不能都删除，要保留⼀个，所以是low +1 = fast977.有序数组的平⽅最爽的莫过于直接所有数求取平⽅，然后排序class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: for i in range(len(nums)): nums[i] = nums[i] ** 2 () return nums只需要注意python中的sort没有返回值，不能直接return ()即可当然我们的⽬的还是使⽤快慢指针处理这道题看看就⾏，时间表现上还不如上⾯的⽅法那： 209.长度最⼩的⼦数组也属于快慢指针的⼀种，不过这种更习惯称其为滑动窗⼝所谓滑动窗⼝，就是不断的调节⼦序列的起始位置和终⽌位置，从⽽得出我们要想的结果。这⾥还是以题⽬中的⽰例来举例，s=7， 数组是 2，3，1，2，4，3，来看⼀下查找的过程：最后找到 4，3 是最短距离。在本题中实现滑动窗⼝，主要确定如下三点：窗⼝内是什么？如何移动窗⼝的起始位置？如何移动窗⼝的结束位置？窗⼝内就是满⾜和>=s的长度最⼩的连续⼦数组窗⼝的起始位置如何移动：如果当前窗⼝内的值⼤于s了，窗⼝就要向前移动了窗⼝的结束位置如何移动：窗⼝的结束位置就是遍历数组的指针。class Solution: def minSubArrayLen(self, s: int, nums: List[int]) -> int: if not nums: return 0 # 右边界最⼤值以及判断条件⽤值 n = len(nums) # 滑动窗⼝左右边界 left = right = 0 # 记录当前元素和 sum = 0 # 记录最短长度 min_len = float('inf') # 循环开始 while right < n: sum += nums[right] # 如果当前元素和 >= s while sum >= s: # 取之前窗⼝长度和当前窗⼝长度最短的 min_len = min(min_len, right - left + 1) # 去掉左侧的数 sum -= nums[left] # 缩⼩窗⼝ left += 1 # 如sum < s，则右指针递增 right += 1 # 如果整个数组所有元素的和相加都 < s # 即不存在符合条件的⼦数组，返回 0 if min_len == float('inf'): return 0 else: return min_len注释认真看下，基本就能了解其思路

2023年8月1日发(作者：)

《labuladong的算法⼩超》A和《代码随想录》B阅读笔记（2）第9天63.不同路径你看，今天就涉及到带有路障的机器⼈运动问题了。先上代码再解析class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: # 构造⼀个DP table row = len(obstacleGrid) col = len(obstacleGrid[0]) dp = [[0 for _ in range(col)] for _ in range(row)] dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0 if dp[0][0] == 0: return 0 # 如果第⼀个格⼦就是障碍，return 0 # 第⼀⾏初始化 for i in range(1, col): if obstacleGrid[0][i] != 1: dp[0][i] = dp[0][i-1] # 第⼀列初始化 for i in range(1, row): if obstacleGrid[i][0] != 1: dp[i][0] = dp[i-1][0] # 迭代过程 for i in range(1, row): for j in range(1, col): if obstacleGrid[i][j] != 1: dp[i][j] = dp[i-1][j] + dp[i][j-1] #return dp[-1][-1] 也可 return dp[row-1][col-1]在叙述的时候注意区分：输⼊数组的障碍物是1，⽽初始化的dp数组遇到障碍物处初始化为0.⾸先是解决“如果有障碍该怎么办”，当然是对应的dp保持为0确认动态规划的⼏个步骤：dp数组的含义与上道题相同递推公式相同，但因为加⼊了障碍，所以要多⼀步判断，判断不是障碍物之后再进⾏递推初始化相同，但要注意如果在⾏边界和列边界初始化是遇到障碍，则障碍物处保持为0，且障碍物之后的位置都是⽆意义的，因为不可能会遍历到那些位置，因此初始化为什么都可以。遍历顺序相同返回时返回最右下⾓位置。可以选择使⽤[-1][-1]和[m-1][n-1]两种形式。343.整数拆分哇哇哇，这道题可了不得，代码量很少，却是集动态规划的⼤成了可以说class Solution: def integerBreak(self, n: int) -> int: dp = [0] * (n + 1) dp[2] = 1 for i in range(3, n + 1): # 假设对正整数 i 拆分出的第⼀个正整数是 j（1 <= j < i），则有以下两种⽅案： # 1) 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * (i-j) # 2) 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[i-j] for j in range(1, i - 1): dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])) return dp[n]重点就在于注释中提到的：# 假设对正整数 i 拆分出的第⼀个正整数是 j（1 <= j < i），则有以下两种⽅案：# 1) 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * (i-j)# 2) 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[i-j]96.不同的⼆叉搜索树⼆叉搜索树是⼀个有序树：若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；它的左、右⼦树也分别为⼆叉搜索树class Solution: def numTrees(self, n: int) -> int: dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): for j in range(1, i + 1): dp[i] += dp[j - 1] * dp[i - j] return dp[-1]说实话，后⾯的这两道题没什么意思，有时间不如就直接背下来算了，我们还是看点有意思的动态规划：背包问题背包问题分类对于⾯试的话，其实掌握01背包，和完全背包，就够⽤了，最多可以再来⼀个多重背包。⾄于背包九讲其其他背包，⾯试⼏乎不会问，都是竞赛 级别的了，leetcode上连多重背包的题⽬都没有，所以题库也告诉我们，01背包和完全背包就够⽤了。⽽完全背包⼜是也是01背包稍作变化⽽来，即：完全背包的物品数量是⽆限的。所以背包问题的理论基础重中之重是01背包，所以⼀定要理解透。⼆维数组解决01背包问题1.确定dp数组以及下标的含义：dp[i][j] 表⽰从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少。2.确定递推公式：回顾⼀下dp[i][j]的含义：从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少。那么可以有两个⽅向推出来dp[i][j]，不放物品i：由dp[i - 1][j]推出，即背包容量为j，⾥⾯不放物品i的最⼤价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量⼤于背包j的重量时，物品i⽆法放进背包中，所以被背包内的价值依然和前⾯相同。)放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最⼤价值，那么dp[i - 1][j -weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最⼤价值。所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);注意dp[i][j]表⽰的是价值3.初始化：⾸先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，⽆论是选取哪些物品，背包价值总和⼀定为0。状态转移⽅程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就⼀定要初始化。dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最⼤价值。那么很明显当 j < weight[0]的时候，dp[0][j]应该是 0，因为背包容量⽐编号0的物品重量还⼩。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放⾜够放编号0物品。即i⽅向初始化为0，j⽅向初始化为最⼩价值，其余位置可初始化为任意值。4.遍历顺序：先遍历物品后遍历背包和先遍历背包后遍历物品没什么区别。虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上⾓，根本不影响dp[i][j]公式的推导！但先遍历物品再遍历背包这个顺序更好理解。第10天复习⼆维数组解决背包问题def test_2_wei_bag_problem1(bag_size, weight, value) -> int:

rows, cols = len(weight), bag_size + 1 dp = [[0 for _ in range(cols)] for _ in range(rows)]

# 初始化dp数组.

for i in range(rows):

dp[i][0] = 0 first_item_weight, first_item_value = weight[0], value[0] for j in range(1, cols):

if first_item_weight <= j:

dp[0][j] = first_item_value # 更新dp数组: 先遍历物品, 再遍历背包.

for i in range(1, len(weight)):

cur_weight, cur_val = weight[i], value[i] for j in range(1, cols):

if cur_weight > j: # 说明背包装不下当前物品.

dp[i][j] = dp[i - 1][j] # 所以不装当前物品.

else:

# 定义dp数组: dp[i][j] 前i个物品⾥，放进容量为j的背包，价值总和最⼤是多少。 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight]+ cur_val) print(dp)if __name__ == "__main__":

bag_size = 4 weight = [1, 3, 4] value = [15, 20, 30] test_2_wei_bag_problem1(bag_size, weight, value)背包问题：⼀维数组解决使⽤的是滚动数组，可以理解为⼆维数组的状态压缩，但我觉得理解起来倒是不难，可以这样理解：在使⽤⼆维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。其实可以发现如果把dp[i - 1]那⼀层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])。与其把dp[i - 1]这⼀层拷贝到dp[i]上，不如只⽤⼀个⼀维数组了，只⽤dp[j]（⼀维数组，也可以理解是⼀个滚动数组）。这是抽象的理解，其实从dp数组的含义上理解也可以。1.确定dp数组的定义：在⼀维dp数组中，dp[j]表⽰：容量为j的背包，所背的物品价值可以最⼤为dp[j]。2.递推公式：dp[j]为容量为j的背包所背的最⼤价值，dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表⽰容量为j - weight[i]的背包所背的最⼤价值。dp[j - weight[i]] + value[i] 表⽰ 容量为 j - 物品i重量的背包加上物品i的价值。（也就是容量为j的背包，放⼊物品i了之后的价值即：dp[j]）此时dp[j]有两个选择，⼀个是取⾃⼰dp[j] 相当于⼆维dp数组中的dp[i-1][j]，即不放物品i，⼀个是取dp[j -weight[i]] + value[i]，即放物品i，指定是取最⼤的，毕竟是求最⼤价值，所以递归公式为：dp[j] = max(dp[j], dp[j - weight[i]] +value[i]);可以看出相对于⼆维dp数组的写法，就是把dp[i][j]中i的维度去掉了。数组的初始化：dp[j]表⽰容量为j的背包，所背的物品价值可以最⼤为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最⼤价值就是0。因为dp数组在推导的时候⼀定是取价值最⼤的数，如果题⽬给的价值都是正整数，那么其余位置就都初始化为0就可以了。这样才能让dp数组在递归的过程中始终去最⼤的值，⽽不是被初始值覆盖了。数组的遍历顺序：⼆维dp遍历的时候，背包容量是从⼩到⼤，⽽⼀维dp遍历的时候，背包是从⼤到⼩。为什么呢？倒序遍历是为了保证物品i只被放⼊⼀次！。但如果⼀旦正序遍历了，那么物品0就会被重复加⼊多次！举⼀个例⼦：物品0的重量weight[0] = 1，价值value[0] = 15，如果正序遍历for(int i = 0; i < (); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); }}dp[1] = dp[1 - weight[0]] + value[0] = 15dp[2] = dp[2 - weight[0]] + value[0] = 30此时dp[2]就已经是30了，意味着物品0，被放⼊了两次，所以不能正序遍历。这是由于先遍历物品然后遍历背包容量⽽固定造成的。代码⽰范def test_1_wei_bag_problem(): weight = [1, 3, 4] value = [15, 20, 30] bag_weight = 4 # 初始化: 全为0 dp = [0] * (bag_weight + 1) # 先遍历物品, 再遍历背包容量 for i in range(len(weight)): for j in range(bag_weight, weight[i] - 1, -1): # 递归公式 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) print(dp)test_1_wei_bag_problem()dp数组的⼤⼩设定为bag_weight是因为包括了背包容量为0的情况其中第⼆层for循环中的右边界就只是weight[i]才对，但因为python的特性是左闭右开的，所以要减1递推公式可以理解为：背包现在状态下的价值和加⼊这个物品后的价值哪个更⼤。细节1是如果该物品的质量⼤于背包剩余质量，是不进⼊循环的。细节2是加⼊物品后要对应的和减去该物品质量后的那个背包状态下的价值去⽐较。第11天416.分割等和⼦集这道题主要体会问题转化为背包问题的思路，可以这样理解：背包质量为sum/2的情况下，最⼤(重量)能装下的物品的价值是否与sum/2相等。换句话说，只要你能在dp[-1]出找到值等于sum/2的情况，那么选取元素之外的剩余元素的和⼀定也是sum/2。dp[i]的数值⼀定是⼩于等于i的。如果dp[i] == i 说明，集合中的⼦集总和正好可以凑成总和i，理解这⼀点很重要。数组含义：dp[j]表⽰容量为j的背包，所背的物品价值可以最⼤为dp[j]。2.递推公式：dp[j] = max( dp[j], dp[j - weight[i]] + value[i] )这么看，这与01背包的唯⼀差别只是在返回值，代码⽰例：class Solution: def canPartition(self, nums: List[int]) -> bool: ji = nums

target = sum(ji) if target%2 != 0:return False

total_bag = target // 2 #print(total_bag)

dp = [0] * (total_bag+1 )

for i in range(len(ji)):

for j in range(total_bag, ji[i]-1,-1): dp[j] = max( dp[j], dp[j - ji[i]]+ji[i] ) return dp[total_bag] == total_bag

3.初始化：从dp[j]的定义来看，⾸先dp[0]⼀定是0。如果如果题⽬给的价值都是正整数那么⾮0下标都初始化为0就可以了，如果题⽬给的价值有负数，那么⾮0下标就要初始化为负⽆穷。这样才能让dp数组在递归公式的过程中取的最⼤的价值，⽽不是被初始值覆盖了。本题题⽬中 只包含正整数的⾮空数组，所以⾮0下标的元素初始化为0就可以了。4.遍历顺序：仍然是先遍历物品，然后遍历背包。1049.最后⼀块⽯头的重量II就这道题吧，让我想基本是想不出来的，看了题解后转化为416.分割等和⼦集问题后我能看得明⽩基本过程与上道题的思路⼏乎⼀样，唯⼀的差别在return处，我们详细的了解下本题其实就是尽量让⽯头分成重量相同的两堆，相撞之后剩下的⽯头最⼩，这样就化解成01背包问题了。最后dp[target]⾥是容量为target的背包所能背的最⼤重量。那么分成两堆⽯头，⼀堆⽯头的总重量是dp[target]，另⼀堆就是sum -dp[target]。在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] ⼀定是⼤于等于dp[target]的。那么相撞之后剩下的最⼩⽯头重量就是 (sum - dp[target]) - dp[target]。class Solution: def lastStoneWeightII(self, stones: List[int]) -> int: sum_tmp = sum(stones) #if sum_tmp%2 != 0: # return False half_sum = sum_tmp // 2 dp = [0] * (half_sum+1) for i in range(len(stones)): for j in range(half_sum, stones[i]-1, -1): dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]) return sum_tmp - 2*dp[half_sum]494.⽬标和这道题也可以说是神分析了本题要如何使表达式结果为target，既然为target，那么就⼀定有 left组合 - right组合 = target。left + right等于sum，⽽sum是固定的。公式来了， left - (sum - left) = target -> left = (target + sum)/2 。target是固定的，sum是固定的，left就可以求出来。此时问题就是在集合nums中找出和为left的组合。竟然就转化为了和上⾯两道题相同的思路先放代码class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: sumValue = sum(nums) if target > sumValue or (sumValue + target) % 2 == 1: return 0 bagSize = (sumValue + target) // 2 if bagSize <0: return 0 dp = [0] * (bagSize + 1) dp[0] = 1 for i in range(len(nums)): for j in range(bagSize, nums[i] - 1, -1): dp[j] += dp[j - nums[i]] return dp[bagSize]dp数组的含义：dp[j]表⽰填满 j 这么⼤容积的包，有 dp[j] 种⽅法确定递推公式：填满容量为j - nums[i]的背包，有dp[j - nums[i]]种⽅法。那么只要搞到nums[i]的话，凑成dp[j]就有dp[j - nums[i]] 种⽅法。举⼀个例⼦,nums[i] = 2： dp[3]，填满背包容量为3的话，有dp[3]种⽅法。那么只需要搞到⼀个2（nums[i]），有dp[3]⽅法可以凑齐容量为3的背包，相应的就有多少种⽅法可以凑齐容量为5的背包。那么需要把 这些⽅法累加起来就可以了，dp[j] += dp[j -nums[i]]

dp[j] += dp[j - nums[i]] ，这是⾸次接触到不同的递推公式，要注意递推公式的具体含义，每道题都要捋顺⼀下递推公式。在这道题中式计算⽅法的总和，所以⼀定是得到的⽅法相加。如果求解最⼩的那种⽅法就是之前的递推公式。初始化：dp[0] = 1，其余初始化为0遍历顺序：同上第12天474.⼀和零倒像是⼀道脑筋急转弯还是要锻炼那个能⼒，直接将dp数组抽象为题⽬中描述的结果，然后去思考怎么递推、怎么初始化、怎么遍历。dp数组含义：最多有i个0和j和1的strs的最⼤⼦集的⼤⼩是dp[i][j]递推公式：判断dp[i][j]与dp[i - zeroNum][j - oneNum]+1⼤⼩，即dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum]+1)初始化为0仍然是遍历物品再遍历背包class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: dp = [[0] * (n + 1) for _ in range(m + 1)] # 默认初始化0 # 遍历物品 for str in strs: ones = ('1') zeros = ('0') # 遍历背包容量且从后向前遍历！ for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1) return dp[m][n]完全背包理论01背包和完全背包唯⼀不同就是体现在遍历顺序上，所以我们可以直接针对遍历顺序经⾏分析！⾸先在回顾⼀下01背包的核⼼代码for(int i = 0; i < (); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); }}我们知道01背包内嵌的循环是从⼤到⼩遍历，为了保证每个物品仅被添加⼀次。⽽完全背包的物品是可以添加多次的，所以要从⼩到⼤去遍历，即// 先遍历物品，再遍历背包for(int i = 0; i < (); i++) { // 遍历物品 for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); }}再次基础上还要注意⼀下for循环的前后顺序，完全背包问题⼀般情况下这个顺序是不影响什么的，但根据题意还是要具体分析19.零钱兑换IIclass Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1

for i in range(len(coins)): for j in range(coins[i], amount+1): dp[j] += dp[j-coins[i]] return dp[-1]dp数组的含义：背包容量为j时凑成总⾦额的硬币组合数为dp[j]递推公式：dp[j] += dp[ j - coins[i] ]初始化：j=0时的硬币凑成⽅式只有⼀种(不进⾏凑硬币这项活动)，其余初始化为0遍历顺序：先遍历物品(从0到len(coins)的所有)，然后遍历价值(重量)，从coins[i]到最⼤的amount,由于python语⾔的特性，所以需要+1。⾃⼰⼼⾥推导⼀遍dp数组递推过程：⽆误第⼗三天377.组合总和IV组合总和的I、II、III，都是使⽤回溯算法求解的，⽽这道IV是以动态规划⽅式求解的，究其原因是因为这⾥需要求解组合数，⼀定意义上这也是⼀种求极值的形式(求最⼤能组合成多少种组合)，所以可以使⽤动态规划求解。此外，题⽬要求中“元素相同但顺序不同也被视为不同组合”，那么其实就是在求排列。数组的含义：选取凑成 j 时的组合数有dp[ j ]种2.递推公式：dp[j] = dp[j - nums[i]]3.初始化：求装满背包⼀共有多少种⽅法，应该是dp = [ 0 ] * (target + 1) ; dp[ 0 ] = 1;

4.遍历顺序：个数不限使⽤，说明是⼀个完全背包。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。如果把遍历nums(物品)放在外循环，遍历target作为内循环的话，举⼀个例⼦：计算dp[4]的时候，结果集只有[1, 3]这样的组合，不会有[3, 1]这样的组合，因为nums遍历在外层，3只出现在1的后⾯。

所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。5.举例dp数组的推导过程class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: dp = [0] * (target+1) dp[0] = 1 for i in range(1, target+1): for j in nums: if i>=j: dp[i] += dp[i-j] return dp[-1]注意先遍历背包再遍历物品的时候要多⼀步if i >= j的判断。

背包问题⼩结dp数组的含义：通常直奔主题；多数采⽤⼀维数组，少数使⽤⼆维数组。递推公式：求解最⼩值时⼤概率使⽤dp[ j ] = max( dp[j], dp[ j ][ j - wights[i] ] + value[i] )或者dp[ j ] = max( dp[j], dp[ j ][ j -wights[i] ] + 1 )；求解组合个数通常使⽤dp[j] = dp[j - nums[i]]。初始化：机器⼈问题初始化是先初始化⾸⾏，再初始化⾸列，其余元素初始化为0；计算个数时⾸元素初始化为1，其余元素初始化为0。遍历顺序：基本都是先遍历物品再遍历背包，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。。此外如果是01背包，则两道for循环是倒序遍历。如果是完全背包，则两道for循环是顺序遍历。70.爬楼梯今天我们使⽤动态规划写⼀下爬楼梯这道题的改进版：你可以⼀步⼀个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的⽅法可以爬到楼顶呢？学完动态规划，呀！我看看这是谁啊，这不是求组合数(多少种⽅法爬到楼顶)吗，这不正是⼀个状态转移的问题吗。仔细想⼀下可以发现，这和上⼀道题就是⼀摸⼀样的了。class Solution: def climbStairs(self, n: int) -> int: dp = [0]*(n + 1) dp[0] = 1 m = 2 # 遍历背包 for j in range(n + 1): # 遍历物品 for step in range(1, m + 1): if j >= step: dp[j] += dp[j - step] return dp[n]第14天322.零钱兑换这道题可以⽤来⽤来检验到⽬前为⽌动规算法的掌握程度，可以根据上⾯的背包问题⼩结试试写代码。dp数组的含义：凑成总⾦额为 j 需要硬币最少dp[j]个。根据dp数组含义，递推公式应为：dp [j] = max(dp[j], dp[j-coins[i]] +1)初始化：dp⼤⼩应amount + 1，dp[0]=1，因为凑成总额为0的硬币个数⼀定为0个，其余初始化为⽆穷⼤，因为递推过程中不能⼀定要覆盖初始化。遍历顺序：因为是可重复使⽤，所以是完全背包，则两层for循环是正向的。求得是组合数⽽不是排序数，则先遍历物品。举例递归：如果⼼算觉得不太清晰，不如就直接写代码输出dp观察结果。写代码：会发现写得很顺畅class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('INF')] * (amount+1) dp[0] = 0 for i in range(len(coins)): for j in range(coins[i], amount+1): dp[j] = min(dp[j-coins[i]]+1, dp[j]) if dp[amount]==float('INF'): return -1 return dp[amount]279.完全平⽅数可能刚看这种题感觉没啥思路，⼜平⽅和的，⼜最⼩数的。把题⽬翻译⼀下：完全平⽅数就是物品（可以⽆限件使⽤），凑个正整数n就是背包，问凑满这个背包最少有多少物品？感受出来了没，这么浓厚的完全背包氛围，和上⼀道题就是⼀样⼀样的！动规五部曲分析如下：确定dp数组（dp table）以及下标的含义：dp[j]：和为j的完全平⽅数的最少数量为dp[j]确定递推公式：dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。此时我们要选择最⼩的dp[j]，所以递推公式：dp[j] =min(dp[j - i * i] + 1, dp[j]);dp数组如何初始化：dp[0]表⽰ 和为0的完全平⽅数的最⼩数量，那么dp[0]⼀定是0。那0 * 0 也算是⼀种啊，为啥dp[0] 就是 0呢？看题⽬描述，找到若⼲个完全平⽅数（⽐如 1, 4, 9, 16, ...），题⽬描述中可没说要从0开始，dp[0]=0完全是为了递推公式。⾮0下标的dp[j]应该是多少呢？从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最⼩的，所以⾮0下标的dp[j]⼀定要初始为最⼤值，这样dp[j]在递推的时候才不会被初始值覆盖。确定遍历顺序：我们知道这是完全背包，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。本题也是⼀样的，是求最⼩数。所以本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！class Solution: def numSquares(self, n: int) -> int: nums = [i**2 for i in range(1, n+1) if i**2 <=n] dp = [float('INF')] * (n+1) dp[0] = 0 for num in nums: for j in range(num, n+1): dp[j] = min(dp[j], dp[j-num]+1) return dp[n]139.单词拆分和之前做过的回溯算法：分割回⽂串⽐较类似。在思考是不是回溯和动规的区别就是回溯是输出所有的情况的具体表现，⽽动规是输出最⼤最⼩的那种情况或者是情况的总数。确定dp数组以及下标的含义：dp[i] : 字符串长度为i的话，dp[i]为true，表⽰可以拆分为⼀个或多个在字典中出现的单词。确定递推公式：如果确定dp[j] 是true，且 [j, i] 这个区间的⼦串出现在字典⾥，那么dp[i]⼀定是true。（j < i ）。所以递推公式是 if([j, i]这个区间的⼦串出现在字典⾥ && dp[j]是true) 那么 dp[i] = true。dp数组如何初始化：从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]⼀定要为true，否则递归下去后⾯都都是false了。那么dp[0]有没有意义呢？dp[0]表⽰如果字符串为空的话，说明出现在字典⾥。但题⽬中说了“给定⼀个⾮空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。下标⾮0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为⼀个或多个在字典中出现的单词。确定遍历顺序：题⽬中说是拆分为⼀个或多个在字典中出现的单词，所以这是完全背包。还要讨论两层for循环的前后循序。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。本题最终要求的是是否都出现过，所以对出现单词集合⾥的元素是组合还是排列，并不在意！那么本题使⽤求排列的⽅式，还是求组合的⽅式都可以。即：外层for循环遍历物品，内层for遍历背包 或者 外层for遍历背包，内层for循环遍历物品 都是可以的。但本题还有特殊性，因为是要求⼦串，最好是遍历背包放在外循环，将遍历物品放在内循环。如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的⼦串都预先放在⼀个容器⾥。（如果不理解的话，可以⾃⼰尝试这么写⼀写就理解了）所以最终我选择的遍历顺序为：遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。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)]第15天704.⼆分查找以这道题为例，讲⼀下⼆分查找的两种代码思路第⼀种写法定义 target 是在⼀个在左闭右闭的区间⾥，也就是[left, right] （这个很重要⾮常重要）。区间的定义这就决定了⼆分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：while (left <= right) 要使⽤ <= ，因为left == right是有意义的，所以使⽤ <=if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]⼀定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1例如在数组：1,2,3,4,7,9,10中查找元素2，如图所⽰：代码及详细的注释：class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums)-1 ##定义target左闭右闭[left, right]的区间内，所以要注意-1 while(left <= right): ##当left==right，区间[left, right]仍然有效 mid = (left + right) // 2 ##取中间值 if nums[mid] > target: ##target在左区间， right = mid - 1 ##所以右边界mid-1 elif nums[mid] < target: ##target在右区间 left = mid + 1 ##所以左边界mid+1 else: ##如果left==right return mid ##则找到了结果 return -1 ##如果遍历之后仍没有找到则返回-1 第⼆种写法如果说定义 target 是在⼀个在左闭右开的区间⾥，也就是[left, right) ，那么⼆分法的边界处理⽅式则截然不同。有如下两点：while (left < right)，这⾥使⽤ < ,因为left == right在区间[left, right)是没有意义的if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，⽽寻找区间是左闭右开区间，所以right更新为middle，即：下⼀个查询区间不会去⽐较nums[middle]在数组：1,2,3,4,7,9,10中查找元素2，如图所⽰：（注意和⽅法⼀的区别）class Solution: def search(self, nums: List[int], target: int) -> int: # 第⼆种写法 left = 0 right = len(nums) ##定义target左闭右开[left, right)的区间内，所以没有-1 while(left < right): ##当left==right，区间[left, right)⽆效，所以没有= mid = (left + right) // 2 ##取中间值 if nums[mid] > target: ##target在左区间， right = mid ##所以右边界mid elif nums[mid] < target: ##target在右区间 left = mid+1 ##所以左边界mid+1 else: ##如果left==right return mid ##则找到了结果 return -1 ##如果遍历之后仍没有找到则返回-(x)本题的题意是：设计⼀个算法求解x的平⽅根可以转化为0-x列举，看看那个数字的平⽅与x⽐较接近class Solution: def mySqrt(self, x: int) -> int: l, r, ans = 0, x, -1 while l <= r: mid = (l + r) // 2 if mid * mid <= x: ans = mid l = mid + 1 else: r = mid - 1 return ans⼤体上遵循上⾯提到的顺序但由于这道题中有可能不会正好取到⼀个整数解⽽是⼀个近似整数解所以我们要把ans放置在⼀个if判断中class Solution: def isPerfectSquare(self, num: int) -> bool: left = 0 right = num while(left<=right): mid = (left + right) //2 if mid * mid == num: return True elif mid * mid < num: left = mid + 1 else: right = mid - 1 return False和上⾯的那道题⼏乎⼀模⼀样，不过由于这次是判断是否为完全平⽅数，因此是有==的情况的，没有的话就直接返回False了。第16天27.移除元素⾸先展⽰下我想到的⼀个特别快的⽅法，哈哈class Solution: def removeElement(self, nums: List[int], val: int) -> int: while (val in nums): (val) return len(nums)快慢指针 def removeElement(self, nums: List[int], val: int) -> int: # 快慢指针法 fast = low = 0 while fast < len(nums): if nums[fast] != val: nums[slow] = nums[fast] slow += 1 # 当fast指针遇到要删除的元素时停⽌赋值 # slow指针停⽌移动，fase指针继续前进 fast += 1 retuen slow从这道题开始，要接触双指针中的快慢指针了。快慢指针，顾名思义就是使⽤相对较快和相对较慢的两个指针在数组上进⾏操作，可在原数组上进⾏遍历⽽不需要开辟额外的空间。需要注意的是：low指针和fast指针的初始位置、if中fast指针的运算和if中元素如何交换这三处在本题中：因为要验证nums数组中和val相等的元素，所以low和fast都初始化为0快慢指针的循环边界⼀般由fast与len(x)来判断fast指针是与val判断相等if语句中要slow和fast处元素交换26.删除有序数组中的重复元素class Solution: def removeDuplicates(self, nums: List[int]) -> int: if not nums: return 0 n = len(nums) fast = 1 low = 0 while fast < n: if nums[fast] != nums[low]: nums[low + 1] = nums[fast] low += 1 fast += 1 return low + 1因为是验证本体数组内元素相等，所以low和fast指针不能相等，⾃然地，fast快了⼀步if中由fast处元素和low处元素⽐较因为重复元素不能都删除，要保留⼀个，所以是low +1 = fast977.有序数组的平⽅最爽的莫过于直接所有数求取平⽅，然后排序class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: for i in range(len(nums)): nums[i] = nums[i] ** 2 () return nums只需要注意python中的sort没有返回值，不能直接return ()即可当然我们的⽬的还是使⽤快慢指针处理这道题看看就⾏，时间表现上还不如上⾯的⽅法那： 209.长度最⼩的⼦数组也属于快慢指针的⼀种，不过这种更习惯称其为滑动窗⼝所谓滑动窗⼝，就是不断的调节⼦序列的起始位置和终⽌位置，从⽽得出我们要想的结果。这⾥还是以题⽬中的⽰例来举例，s=7， 数组是 2，3，1，2，4，3，来看⼀下查找的过程：最后找到 4，3 是最短距离。在本题中实现滑动窗⼝，主要确定如下三点：窗⼝内是什么？如何移动窗⼝的起始位置？如何移动窗⼝的结束位置？窗⼝内就是满⾜和>=s的长度最⼩的连续⼦数组窗⼝的起始位置如何移动：如果当前窗⼝内的值⼤于s了，窗⼝就要向前移动了窗⼝的结束位置如何移动：窗⼝的结束位置就是遍历数组的指针。class Solution: def minSubArrayLen(self, s: int, nums: List[int]) -> int: if not nums: return 0 # 右边界最⼤值以及判断条件⽤值 n = len(nums) # 滑动窗⼝左右边界 left = right = 0 # 记录当前元素和 sum = 0 # 记录最短长度 min_len = float('inf') # 循环开始 while right < n: sum += nums[right] # 如果当前元素和 >= s while sum >= s: # 取之前窗⼝长度和当前窗⼝长度最短的 min_len = min(min_len, right - left + 1) # 去掉左侧的数 sum -= nums[left] # 缩⼩窗⼝ left += 1 # 如sum < s，则右指针递增 right += 1 # 如果整个数组所有元素的和相加都 < s # 即不存在符合条件的⼦数组，返回 0 if min_len == float('inf'): return 0 else: return min_len注释认真看下，基本就能了解其思路