企业官网建设流程全解析

海南省建设网站的公司电话号码,wordpress博客站模板下载,手机网站建设代码,wordpress模块里加载最新文章这道题是经典的一维动态规划问题#xff0c;题目要求#xff1a;给定硬币面额数组 coins 和总金额 amount#xff0c;用最少的硬币数凑出这个金额#xff0c;如果无法凑出则返回 -1。leetcode​ 看起来像是「完全背包」的变体#xff0c;但真正写代码时#xff0c;很多细…这道题是经典的一维动态规划问题题目要求给定硬币面额数组 coins 和总金额 amount用最少的硬币数凑出这个金额如果无法凑出则返回 -1。leetcode​看起来像是「完全背包」的变体但真正写代码时很多细节非常容易出错比如初始值、dp[0] 的含义、不可达状态怎么表示等。leetcode1​本文从一个接近正确但有 bug 的思路出发一步步推导出正确的 DP 解法和代码实现。题意与状态定义题目原文要点如下leetcode​给你一个整数数组 coins表示不同面额的硬币。给你一个整数 amount表示总金额。返回凑成总金额所需的 最少 硬币数如果无法凑成返回 -1。每种硬币的数量可以视为 无限。自然的状态定义是定义 dp[i]凑出金额 i 所需的最少硬币个数。在这个定义下有一个特别关键的点凑出金额 0 不需要任何硬币所以dp[0] 0是唯一合理的取值。如果把 dp[0] 设成 1就会出现dp[coin] min(dp[coin], dp[0] 1)这时 dp[coin] 会被更新为 2意味着凑一个 coin 面额需要两枚硬币这显然不符合题意。初始化与不可达状态有了状态定义就要考虑「还没被凑出来」的金额怎么表示。常见错误是把所有 dp[i] 初始化成 0然后依赖转移去堆加。或者用 INT_MAX 之类的值但在 dp[i - coin] 1 时不考虑溢出或不可达的问题。更安全、易理解的方式是将所有 dp[i] 初始化为一个「不可能达到的上界」比如amount 1。因为最多用 amount 枚面额为 1 的硬币所以 amount 1 一定是无效解。再设置 dp[0] 0表示金额 0 只需要 0 枚硬币。在 C 代码中也可以用 INF_MAX 表示不可达然后在转移时跳过不可达状态。leetcode​示例C 代码中的初始化方式leetcode​使用宏定义一个无限大值#define INF_MAX 0x7fffffff。leetcode​分配数组之后将 dp[0…amount] 全部赋值为 INF_MAX。leetcode​再单独令 dp[0] 0。leetcode​这样当某个金额 i 当前还凑不出来时dp[i] 就会保持为 INF_MAX在做转移时可以通过判断是否等于 INF_MAX 来避免错误使用这个状态。leetcode​转移方程与遍历顺序在一维 DP 下标准的转移方程是对于每个金额 i1 到 amount遍历每个硬币 coin如果 i - coin 0 且 dp[i - coin] 可达那么dp[i] min(dp[i], dp[i - coin] 1)。注意这里有几个细节容易出错不能只遍历大于当前 i 的 coin只有 coin i 的时候才能用于凑金额 i。所以代码中通常写成if (i - coin 0) continue;。leetcode​必须跳过不可达状态如果 dp[i - coin] 还是初始化的「INF」说明金额 i - coin 根本凑不出来。此时不能做 dp[i - coin] 1否则会以垃圾值去更新 dp[i]。C 代码中通过if (dp[i - choice] INF_MAX) continue;来规避。leetcode​遍历顺序这里外层是金额 i内层是硬币 coins[j]属于典型的一维完全背包写法之一leetcode​for i in [1..amount] for each coin因为每个硬币可以重复使用所以不会因为遍历顺序而导致错过组合。最终答案与返回值处理当所有状态都计算完之后答案在 dp[amount] 中如果 dp[amount] 仍然是初始化的「INF」或者 amount 1说明无法凑出该金额返回 -1。否则返回 dp[amount] 即可。在实际 C 实现中代码形态如下与你提交的版本一致leetcode​用 INF_MAX 初始化所有 dp[i]。leetcode​更新完所有状态后通过ret dp[amount] INF_MAX ? -1 : dp[amount];得到最终答案。leetcode​最后记得 free(dp)防止内存泄漏。leetcode​完整 C 实现解析下面是一份通过 LeetCode 所有测试用例的 C 代码它完整体现了上面所有的思路要点leetcode​#includestdlib.h#defineINF_MAX0x7fffffff#defineMIN(a,b)((a)(b)?(a):(b))intcoinChange(int*coins,intcoinsSize,intamount){inti,j,choice,ret;int*dpNULL;dp(int*)malloc((amount1)*sizeof(int));for(i0;iamount;i)dp[i]INF_MAX;// 初始化为不可达状态dp[0]0;// 凑出金额 0 需要 0 枚硬币for(i1;iamount;i){for(j0;jcoinsSize;j){choicecoins[j];if(i-choice0)// 当前硬币面值比金额大跳过continue;if(dp[i-choice]INF_MAX)// 子状态不可达跳过continue;dp[i]MIN(dp[i],dp[i-choice]1);// 状态转移}}retdp[amount]INF_MAX?-1:dp[amount];// 处理答案free(dp);returnret;}这段代码的关键点可以归纳为状态定义清晰dp[i] 表示金额 i 的最少硬币数。初始化严谨不可达用 INF_MAX 表示dp[0] 0。转移安全只有在子状态可达的前提下才尝试更新。返回值合理判断最终状态是否可达决定返回 -1 还是 dp[amount]。面试思路复盘面试官会怎么问你如果在面试中现场推这个题面试官可能会围绕如下几个问题引导你修正思路「你能用一句话准确定义 dp[i] 吗」「当 amount 0 时答案是多少那 dp[0] 应该怎么初始化」「还没被凑出来的金额你准备用什么值表示」「什么时候可以安全地做 dp[i - coin] 1」「在计算 dp[i] 时哪些面额的 coin 对它是有效的遍历条件是什么」只要你能把这些问题回答清楚基本就已经掌握了这道题的核心思路代码也就顺理成章写出来了。总结如果你愿意可以把你之后写的别的语言版本比如 C/Java/Python也贴出来再对照这个 DP 模板做一次统一整理顺便形成一套自己的「完全背包最少数量」模板。https://leetcode.com/problems/coin-change/description/?envTypestudy-plan-v2envIdtop-interview-150https://leetcode.com/problems/coin-change/submissions/1870566313/?envTypestudy-plan-v2envIdtop-interview-150