零钱兑换解法汇总 3.BFS---广度优先遍历 2.动态规划 3.记忆化递归 4.套「完全背包」问题的公式 总结 原题链接: leetcode 322....事实上，可以 直接面对问题求解 ，即「自顶向下」，但是这样的问题有 重复子问题，需要缓存已经求解过的答案，这叫 记忆化递归。...首先在编程中不像生活中一样，我给你一个钱包让你用最少的硬币数组成2元，并且此时我只给你1元硬币和2元硬币，你知道选2构成2。...在编程中我们首先要求出最小子问题，即钱包里面一分钱都不放的结果为0个硬币，显而易见。...下面通过最小子问题求出钱包必须放刚刚好一块钱时的结果，dp[1]=dp[0]+1—假设此时我们位于堆满一元硬币的房间内,显然结果为1。
零钱兑换中，我们求的是「取得特定价值所需要的最小物品个数」。 对于本题，我们求的是「取得特定价值的方案数量」。 求的东西不一样，但问题的本质没有发生改变，同样属于「组合优化」问题。...注意题目描述中是凑成总金额的硬币组合数，为什么强调是组合数呢？ 例如示例一： 5 = 2 + 2 + 1 5 = 2 + 1 + 2 这是一种组合，都是 2 2 1。...那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。 所以这种遍历顺序中dp[j]里计算的是组合数！...---- 记忆化搜索解法 递归的结束条件：凑出了目标钱数，找到了一种方案，返回1 ， 或者枚举完了所有硬币，即越界了，说明当前没有可行方案，返回0 递归返回值:返回当前方案数 本级递归做什么:遍历硬币数组...可能存在的方案数进行累加求和 注意暴力递归会超时，这里还需要用依赖哈希表来存储已经求出来的结果，防止重复计算 其实如果用递归解，最好的方法还是把问题转化为多叉树的遍历，比较容易理解 那么重复计算是从哪里来的呢
如图示:从 2 走到最底下最短路径为 2+3+5+1 = 11,即为我们所求的 首先我们需要用一个二维数组来表示这个三个角形的节点，用二维数组显然可以做到， 第一行的 2 用 a[0][0] 表示，第二行元素...一、判断是否可用递归来解 对于 amount 来说，如果我们选择了 coins 中的任何一枚硬币，则问题的规模(amount)是不是缩小了,再对缩小的 amount 也选择 coins 中的任何一枚硬币...,直到再也不能选择（amount <= 0, amount = 0 代表有符合条件的解，小于0代表没有符合条件的解），从描述中我们可以看出问题可以分解成子问题，子问题与原问题具有相同的解决问题的思路，同时也有临界条件...[i] 表示选择了此硬币, 1 表示选择了coins[i] 这一枚硬币 从以上的递推公式中我们可以获取 DP 的解题思路，我们定义 DP(i) 为凑够零钱 i 需要的最小值，状态转移方程如下 DP[...return -1; } return dp[amount]; } 画外音：以上只是求出了凑成零钱的的最小数量，但如果想求由哪些面值的硬币构成的，该如何修改呢？
如图示:从 2 走到最底下最短路径为 2+3+5+1 = 11,即为我们所求的 首先我们需要用一个二维数组来表示这个三个角形的节点，用二维数组显然可以做到， 第一行的 2 用 a[0][0] 表示，第二行元素...一、判断是否可用递归来解 对于 amount 来说，如果我们选择了 coins 中的任何一枚硬币，则问题的规模(amount)是不是缩小了,再对缩小的 amount 也选择 coins 中的任何一枚硬币...coins[i] 这一枚硬币 3、将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中 得出了递推公式用代码实现就简单了，来简单看一下 publicclass Solution {...[i] 表示选择了此硬币, 1 表示选择了coins[i] 这一枚硬币 从以上的递推公式中我们可以获取 DP 的解题思路，我们定义 DP(i) 为凑够零钱 i 需要的最小值，状态转移方程如下 DP[...return -1; } return dp[amount]; } 画外音：以上只是求出了凑成零钱的的最小数量，但如果想求由哪些面值的硬币构成的，该如何修改呢？
按照「从下往上」的顺序，「从解决最小的问题开始」，并把已经解决的小问题的解存储下来（大部分都是存储在一维数组或者二维数组中），然后把小问题的解组合起来逐步解决大问题。...先求出f(0)和f(1)的值， 然后用f(0)和f(1)的值求出f(2) 用f(1)和f(2)的值求出f(3) 依次类推，直至求出f(n-1) function rob(nums){ if(nums.length...的值已经计算出来并保存到dp[j]的位置 此时f(i,j)的值还没有计算出来，因此保存在dp[j+1]中的还是f(i-1,j)的值 ---- 矩阵路径问题 这类问题通常输入是一个「二维的格子」，一个机器人按照一定的规则从格子的某个位置走到另一个位置...创建一个只有两行的二维数组dp，将f(i,j)保存在dp[i&1][j]中，那么将空间复杂度到O(n)。...target(target为sum的一半) 为了避免不必要的重复计算，用二维数组dp保存f(i,j)的计算结果。
,cn-1]：可选的n枚硬币面额值 这个问题有一个最优的子结构性质，这是解决动态规划问题的关键。最优解可以从其子问题的最优解构造出来。如何将问题分解成子问题？...下列递推关系成立： 在上面的递归树中，可以发现有许多子问题被多次计算。例如，F(1)被计算了13次。...为了避免重复的计算，我们将每个子问题的答案存在一个数组中进行记忆化，如果下次还要计算这个问题的值直接从数组中去除返回即可，这样能保证每个子问题最多只被计算一次。...例子1：假设 coins = [1,2,5],amount=11 则，当i==0时无法用硬币组成，为0。...F(11) 3 //F(11)=min(F(11-1),F(11-2),F(11-5))+1=3 我们可以看到问题的答案是通过子问题的最优解得到的 例子2：假设 coins = [1,2,3],amount
因此，在动态规划中，通常会结合其他优化方法，如记忆化搜索、剪枝等，使得算法能够高效求解。...将已解决的子问题的结果保存在一个数组或者哈希表中，当需要计算相同的子问题时，就可以直接返回之前计算的结果，而不必再次递归计算。...在以下代码中，我们初始化一个数组 dp 来存储子问题的解，它起到了记忆化搜索中数组 mem 相同的记录作用。...分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。...动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。
,cn-1]：可选的n枚硬币面额值 这个问题有一个最优的子结构性质，这是解决动态规划问题的关键。最优解可以从其子问题的最优解构造出来。如何将问题分解成子问题？...下列递推关系成立： 在上面的递归树中，可以发现有许多子问题被多次计算。例如，F(1)被计算了13次。...为了避免重复的计算，我们将每个子问题的答案存在一个数组中进行记忆化，如果下次还要计算这个问题的值直接从数组中去除返回即可，这样能保证每个子问题最多只被计算一次。...方法3、动态规划-自下而上： 采用自下而上的方式进行思考，仍定义F(i)为组成金额i所需最少的硬币数量，假设在计算F(i)之前，我们已经计算出F(0)-F(i-1)的答案，则F(i)对应的转移方程为...F(11) 3 //F(11)=min(F(11-1),F(11-2),F(11-5))+1=3 我们可以看到问题的答案是通过子问题的最优解得到的 例子2：假设 coins = [1,2,3],amount
题目：POJ1742 大意：有n种不同大小的硬币，面值是ai每种有mi个，题目问，这些硬币能够在价格1-m之间，付款多少种金额？...这个问题就是dp的多重部分和问题，在定义递推关系的时候，不同的递推关系会影响到复杂度。...或 起来 然而这个算法的复杂度是O(KΣimi)，于是在题目要求下，就tle了 下面是MLE的思路 如果我们不仅求出是否能加和得到目标数值，还顺便把得到这个数的时候，ai还剩下多少个也算出来，那么就可以降低时间复杂度...把dp数组改为： dp[i+1][j]=用前i种数，加和得到j时，第i种数最多还能剩下多少个。...上面这个思路是正确的，但是我们需要开一个很大的二维数组，对于这一题来说，就MLE了 重复利用数组，降低空间复杂度 我们会发现，当我们进行循环时，是按照i，一位一位进行增加的，在计算第i位的时候，i-1位之前的数据其实已经不需要了
3、dp 数组的迭代解法 有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算岂不美哉！...优化方法无非是用备忘录或者 DP table，再无奥妙可言。 这个例子的最后，讲一个细节优化。...比如你想求amount = 11时的最少硬币数（原问题），如果你知道凑出amount = 10的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案，因为硬币的数量是没有限制的...int): # 定义：要凑出金额 n，至少要 dp(n) 个硬币 def dp(n): # 做选择，需要硬币最少的那个结果就是答案 for coin in...-1 : dp[amount]; } PS：为啥dp数组初始化为amount + 1呢，因为凑成amount金额的硬币数最多只可能等于amount（全用 1 元面值的硬币），所以初始化为amount
dp[状态1][状态2][...] = 计算(选择1，选择2...) 第二步要明确dp数组的定义。 首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组。...换句话说，翻译回我们题目的意思就是： 若只使用coins中的前i个硬币的面值，若想凑出金额j，有dp[i][j]种凑法。...因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。 我们最终想得到的答案就是dp[N][amount]，其中N为coins数组的大小。...我用 Java 写的代码，把上面的思路完全翻译了一遍，并且处理了一些边界问题： int change(int amount, int[] coins) { int n = coins.length...[j] = dp[j] + dp[j-coins[i]]; return dp[amount]; } 这个解法和之前的思路完全相同，将二维dp数组压缩为一维，时间复杂度 O(N*amount
若用分治法来解，有些共同部分被重复计算了很多次。如果能够保存已解决的子问题的答案，在需要时再查找，这样就可以避免重复计算、节省时间，也就是解决冗余。...实际应用中尝试解决一个问题时，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据），以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。 什么是状态？...这种技巧，通俗的说叫“花费空间来节省时间”：动态规划就是通过这样的方式“记忆”过去，节省每次重新计算的时间。 我们可以用一个表来记录所有已解的子问题的答案。...最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系依次填写...]，计算这些i中，能产生最大L[i]的i，之后就可以求出L[j]。
1.2、定义 【重点】如果问题是由交叠的子问题构成的，那么就可以用动态规划技术来解决它。 一般来说，子问题出现在对给定问题求解的递推关系中，这个递推关系中包含相同类型的更小子问题的解。...DP建议对于交叠的子问题一次又一次的求解，不如对每个较小的子问题只求解一次并把结果记录在表中，这样就可以从表中得出原始问题的解。...（解决重复计算问题） 或建立DP表自下而上检查子问题的循环/拓扑顺序（状态转移方程） 解原问题：=子问题或通过组合子问题解 =>额外时间 来源：麻省理工针对动态规划推导步骤，动态规划第一篇，动态规划第二篇...2.2、精简下步骤 1、定义子问题-问题拆解 2、构建递推公式（递归+记忆化==>递推） 3、自底向上处理（状态转移方程） 4、DP ≈ 递归+记忆化+猜测 三、学习路线 币值最大化 硬币找零问题（...贪心算法） 硬币收集 暴力递归（贪心失效） 避免递归重复计算（递推=递归+记忆化） 背包问题 完全背包 子数组问题 子序列问题 买卖股票 最长递增子序列问题 最大子数组问题 最优子结构与状态依赖 本文讲解了动态规划的思想的推演以及学习实践路径
现在问题的关键就在于把实际问题抽象化为背包问题中的哪一类，然后套用模板即可。 在以下问题中，模板中的二维数组均可优化为一维数组以降低空间复杂度。...不用加重记忆负担去考虑什么时候该顺序遍历，什么时候该逆序遍历，以及行列遍历顺序能不能颠倒。当你了解了这个模板的含义，知道动态规划是如何在二维数组上实现的，这些问题都可以迎刃而解。...完全背包 从n种物品中任选，每种物品可以无限取用 方案数 518. 零钱兑换 II 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。...组合总和 Ⅳ 给你一个由不同整数组成的数组nums，和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。 题目数据保证答案符合 32 位整数范围。...添加的数位中没有数字 0 。 由于答案可能会很大，请你以字符串形式返回。 如果按照上述要求无法得到任何整数，请你返回 “0” 。
在代码中，我们使用了一个二维数组dp来记录子问题的结果，通过填表的方式逐步求解dp[i][j]的值。最终返回dp[m][n]即可得到最长公共子序列的长度。...假设割断点在j处（1 <= j <= i），则割断后的两段钢条分别为长度为j的钢条和长度为i-j的钢条。割断后的总价值为价值表中对应长度的价值之和，即price[j] + dp[i-j]。...在某些情况下，状态转移方程的计算量较大，可能导致更高的时间复杂度。 空间复杂度分析： 自底向上的动态规划通常需要使用一个二维数组或更高维的状态表来存储中间结果。...解题思路： 统计字符集中每个字符出现的频率，并构建字符频率表。 创建一个优先队列（通常使用最小堆），将字符频率表中的字符按照频率从小到大依次加入队列。...Tip：动态规划和贪心算法并不是相互排斥的，有些问题既可以用动态规划求解，也可以用贪心算法求解。在实际应用中，根据问题的特性和要求，选择合适的算法进行求解。
动态规划和递归的区别：递归和回溯可能存在非常多的重复计算，动态规划可以用递归加记忆化的方式减少不必要的重复计算动态规划的解题方法递归+记忆化(自顶向下)动态规划（自底向上）图片解动态规划题目的步骤根据重叠子问题定义状态寻找最优子结构推导状态转移方程确定...[row - 1][col - 1]};0-1背包问题0-1背包问题指的是有n个物品和容量为j的背包，weight数组中记录了n个物品的重量，位置i的物品重量是weighti，value数组中记录了n个物品的价值...j的背包，当dp[i][j]为true时表示恰好可以装满 //最后求的是 dp[n][sum] 表示前n个物品能否把容量为sum的背包恰好装满 //dp数组长度是n+1，而且是二维数组，第一维表示物品的索引...7，在用2个1，4 * 7 + 2 * 1 = 30，但是我们用5个6，5 * 6 = 30 就能用最少的硬币兑换完成方法1.动态规划思路：dp[i]表示兑换面额i所需要的最少硬币，因为硬币无限，所以可以自底向上计算...dp[i]，对于dp[0~i]的每个状态，循环coins数组，寻找可以兑换的组合，用i面额减去当前硬币价值，dp[i-coin]在加上一个硬币数就是dp[i],最后取最小值就是答案，状态转移方程就是dp
动态规划和递归的区别：递归和回溯可能存在非常多的重复计算，动态规划可以用递归加记忆化的方式减少不必要的重复计算动态规划的解题方法递归+记忆化(自顶向下)动态规划（自底向上）图片解动态规划题目的步骤根据重叠子问题定义状态寻找最优子结构推导状态转移方程确定...空间复杂度是O(mn) ，需要用m * n大小的二维数字存储状态。...7，在用2个1，4 * 7 + 2 * 1 = 30，但是我们用5个6，5 * 6 = 30 就能用最少的硬币兑换完成方法1.动态规划思路：dp[i]表示兑换面额i所需要的最少硬币，因为硬币无限，所以可以自底向上计算...dp[i]，对于dp[0~i]的每个状态，循环coins数组，寻找可以兑换的组合，用i面额减去当前硬币价值，dp[i-coin]在加上一个硬币数就是dp[i],最后取最小值就是答案，状态转移方程就是dp...0-1背包问题指的是有n个物品和容量为j的背包，weight数组中记录了n个物品的重量，位置i的物品重量是weighti，value数组中记录了n个物品的价值，位置i的物品价值是vales[i]，每个物品只能放一次到背包中
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
