三河市住房与建设局网站,广州天河区注册公司,编程游戏,网站建设用那个软件322. 零钱兑换
想象你有一堆不同面值的硬币#xff0c;现在的任务是用这些硬币凑出一个指定的金额#xff0c;比如说11元#xff0c;而且要求用的硬币数量尽可能少。 准备工作#xff1a;首先#xff0c;我们做了一张表#xff08;叫dp#xff09;#xff0c;这张表记…322. 零钱兑换
想象你有一堆不同面值的硬币现在的任务是用这些硬币凑出一个指定的金额比如说11元而且要求用的硬币数量尽可能少。 准备工作首先我们做了一张表叫dp这张表记录了从0元到目标金额比如11元每一个金额所需要的最少硬币数量。刚开始我们假设每个金额所需的硬币数量都是最多的这就像是一个最坏的情况。 开始计算然后我们开始尝试用手头上的每一种硬币去更新这张表。对于每一种硬币我们看它能帮助减少哪些金额所需的硬币数量。 比如如果我们有1元和2元的硬币我们就从1元和2元开始一直尝试到11元看看加入这种硬币后能不能让所需硬币数量更少。每次当我们考虑加入一个新的硬币时我们会查看如果我现在用这个硬币再加上剩下的金额所需要的最少硬币数这个信息已经在表里了是不是比目前记录的要少。如果是就更新这个金额所需的最少硬币数。 结果判断最后我们看看表中记录的目标金额所需的硬币数量是否被更新过如果没有被更新过说明用这些硬币凑不出这个金额如果能凑出来就告诉你需要的最少硬币数是多少。
class Solution:def coinChange(self, coins: List[int], amount: int) - int:# 初始化从0到目标金额的逐个列表dp [amount1 for _ in range(amount1)]dp[0] 0 # 金额0不要任何硬币# 遍历每个硬币for c in coins:# 遍历大于等于硬币面额的金额for i in range(c, amount1):# 核心更新当前金额的最少所需硬币数求 只使用当前硬币的数量 和 使用一个当前硬币差额所需的最小硬币数 的最小值dp[i] min(dp[i], dp[i-c]1)# 如果指定金额的硬币数没有被更新说明没有组合能够满足return dp[-1] if dp[-1] ! amount1 else -1
dp[i] min(dp[i], dp[i-c]1) 这行代码是动态规划的核心。dp[i-c]1表示如果你选择了面额为c的硬币那么对于剩余的金额i-c所需的最小硬币数就是dp[i-c]再加上你这次选择的这一枚硬币也就是1。min(dp[i], dp[i-c]1)的意思是比较当前金额i所需最小硬币数的现有值dp[i]和使用当前面额硬币新计算得到的值dp[i-c]1取二者中的较小值作为新的最小硬币数。
78. 子集
以nums [1, 2, 3]为例。想象一下我们有一个空盒子temp我们可以决定是否要把一些数字放进去。我们的目标是找出所有可能的方式来填充这个盒子也就是所有的子集。
开始时我们的盒子是空的。这也是一个子集所以我们先把它加到结果列表res中。现在res [[]]。 递归的魔法我们用一个函数dfs来帮助我们决定每个数字是否放入盒子。 我们从第一个数字开始看看我们可以把它放入盒子即列表temp然后我们继续看下一个数字。 每当我们考虑一个数字比如1我们会做两件事一次尝试把它加入盒子另一次则不加。对于每种情况我们都会继续向下看下一个数字直到没有更多数字为止。 添加子集每次我们到达数字列表的末尾时我们的盒子里装的就是一个完整的子集。我们把这个子集的一个复制使用list(temp)来确保我们复制的是内容而不是引用加到结果res中。 回溯这个词听起来有点复杂但实际上很简单。就是当我们考虑完一个数字比如1放入盒子后我们会把它拿出来temp.pop()就好像我们从未做过这个决定一样。这样我们就可以回到之前的状态然后考虑不放入1的情况。这个过程让我们能够探索所有可能的组合。 结束当我们考虑完所有的数字后res就包含了所有可能的子集。
class Solution:def subsets(self, nums: List[int]) - List[List[int]]:res []def dfs(temp, index, nums):# 直接添加当前子集到结果列表中无需等到最后res.append(list(temp)) # 使用list(temp)来复制当前子集# 遍历从当前索引到末尾的所有元素for i in range(index, len(nums)):# 包含当前元素temp.append(nums[i])# 递归调用处理下一个元素dfs(temp, i 1, nums)# 回溯移除当前元素尝试下一个选择temp.pop()# 开始递归dfs([], 0, nums)return(res)221. 最大正方形
定义状态我们可以定义一个二维的DP数组dp其中dp[i][j]代表以(i, j)为右下角的最大正方形的边长。注意这个定义是关键的因为它让我们能够通过左边、上边和左上角的状态来决定当前位置的状态。 找到状态转移方程对于每个位置(i, j)如果该位置的值是’1’那么dp[i][j]应该是其左边、上边和左上角的dp值中的最小值加1。这是因为一个位置如果要构成一个更大的正方形它的左边、上边和左上角也必须能构成正方形。数学表达式为dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1。 初始化对于矩阵的第一行和第一列dp[i][j]就直接是矩阵中的值因为它们只能形成最大边长为1的正方形。 遍历矩阵填充DP数组从(1, 1)开始遍历整个矩阵并根据状态转移方程更新DP数组。 找到最大的dp[i][j]遍历DP数组找到最大的值这个值的平方即为最大正方形的面积。 创建了一个辅助矩阵元素是int这样就解决了对原始矩阵元素转换类型的问题同时还有在原始矩阵里修改元素影响实际计算的问题。然后针对元素为’1’时才开始计算同时考虑边界情况。状态转移方程是根据每一步前面的上、左、左上角的累计最小值1决定当前1的边长这样在本身自己是一个单位的基础上和上面的合起来就是2依次累加 class Solution:def maximalSquare(self, matrix: List[List[str]]) - int:# 长宽初始化最大边长rows,cols len(matrix), len(matrix[0])max_side 0# 辅助矩阵全0初始化dp [[0]*cols for _ in range(rows)] # 遍历每个元素for r in range(rows):for c in range(cols):if matrix[r][c] ! 0: # 为1才进行计算if r 0 or c 0: # 对于边界情况进行处理dp[r][c] 1else: # 状态转移方程假设当前是正方形的右下角其值由左、上、左上的最小值决定dp[r][c] min(dp[r][c-1], dp[r-1][c], dp[r-1][c-1]) 1# 更新最大边长max_side max(max_side, dp[r][c])# 边长2次方return max_side ** 2
