建站购物网站,杭州传媒公司,北京注册公司需要什么,贵州省健康码二维码图片下载概述
#xff08;确定状态#xff09;确定问题状态 提炼最后一步子问题转化 #xff08;求得方程#xff09;转移方程#xff0c;把问题方程化#xff08;设初置界#xff09;按照实际逻辑设置初始条件和边界情况#xff08;确序再解#xff09;确定计算顺序并求解
…概述
确定状态确定问题状态 提炼最后一步子问题转化 求得方程转移方程把问题方程化设初置界按照实际逻辑设置初始条件和边界情况确序再解确定计算顺序并求解
一个案例最少硬币组合
你打算买一本27元的书你现有三种硬币分别面值2元5元和7元每种硬币都充足。请问如何用个数最少的硬币组合正好付清
正常人第一反应思路:
最少硬币组合?
优先使用大面值硬币 —— 777526不符合求解目标27元。换种组合 —— 77722227总共用了6枚硬币正好27元。实际正确答案 —— 7555527才用了5枚硬币。
所以这里贪心算法是并不适用。
题目中关键词“最少的”这是用到“动态规划”的味道。
解决动态规划问题4步
第一步确定问题状态
动态规划问题求解需要先开一个数组并确定数组的每个元素f[i]代表什么这就是确定这个问题的状态。这类似于解数学题中设定xyz代表什么。
A、确定状态首先提取“最后一步”
最优策略必定是K枚硬币a1, a2, …, aK面值加起来是27。
找出不影响最优策略的最后一个独立角色这道问题中那枚最后的硬币aK就是最后一步。把aK提取出来硬币aK之前的所有硬币面值加总是27-aK。因为总体求最硬币数量最少策略所以拼出27-aK的硬币数也一定最少重要设定。 B、转化子问题
最后一步aK提出来之后我们只要求出“最少用多少枚硬币可以拼出27- aK”就可以了。
这种与原问题内核一致但是规模变小的问题叫做子问题。
为简化定义我们设状态f(X)最少用多少枚硬币拼出总面值X。
我们目前还不知道最后的硬币aK面额多少但它的面额一定只可能是{2, 5, 7}之一。
如果aK是2f(27)应该是f(27-2) 1(加上最后这一枚面值2的硬币如果aK是5f(27)应该是f(27-5) 1(加上最后这一枚面值5的硬币如果aK是7f(27)应该是f(27-7) 1(加上最后这一枚面值7的硬币
除此以外没有其他的可能了。至此通过找到原问题最后一步并将其转化为子问题。
为求面值总额27的最小的硬币组合数的状态就形成了用以下函数表示
f(27) min{f(27-2)1, f(27-5)1, f(27-7)1}第二步转移方程把问题方程化
f[X] min{f[X-2]1, f[X-5]1, f[X-7]1}动态规划都是要开数组所以上面式子改用方括号表示。实际求解动态规划类问题正确列出转移方程正确基本上就解决一半了。
递归的解法
// f(X)返回最少用多少枚硬币拼出X
int f(int X) {// 0元钱只要0枚硬币if (X 0) return 0;// 初始化用无穷大int res Integer.MAX_VALUE;// 最后一枚硬币是2元if (X 2) {res Math.min(f(X – 2) 1, res);}// 最后一枚硬币是5元if (X 5) {res Math.min(f(X – 5) 1, res);}// 最后一枚硬币是7元if (X 7) { res Math.min(f(X – 7) 1, res);}return res;
}执行图如下 要算f(27)就要递归f(25)、f(22)、f(20)然后下边依次递归。 问题明显重复递归太多。
这是求f(27)等待时间还可以接受。如果求f(100)呢
求总体最值可优先考虑动态规划不要贸然去递归。
第三步按照实际逻辑设置边界情况和初始条件。
如果不按照实际逻辑设置边界情况和初始条件即使转移方程正确也大概率无法跑通代码。
f[X] min{f[X-2]1, f[X-5]1, f[X-7]1}的边界情况是[x-2]、[x-5]、[x-7]不能小于0硬币面值为正也不能高于27。
故对边界情况设定如下
如果硬币面值不能组合出Y就定义f[Y]正无穷。例如f[-1] f[-2] … 正无穷f[1] min{f[-1]1, f[-4]1,f[-6]1} 正无穷特殊情况本题的F[0]对应的情况为F[-2]、F[-5]、F[-7]按照上文的边界情况设定结果是正无穷但是实际上F[0]的结果是存在的即使用0个硬币的情况下F[0]0。
可是按照我们刚刚的设定F[0]F[0-2]1 F[-2]1正无穷。岂不是矛盾这种用转移方程无法计算但是又实际存在的情况就必须通过手动定义。这里手动强制定义初始条件为F[0]0。
而从0之后的数值是没矛盾的比如F[1] F[1-2]1 F[-1]1正无穷正无穷加任何数结果还是正无穷F[2] F[2-2]1 F[0]11。
第四步确定计算顺序并计算求解
那么开始计算时是从F[1]、F[2]开始呢还是从F[27]、F[26]开始呢
判断计算顺序正确与否的原则是当我们要计算F[X]等式左边如F[10]的时候等式右边f[X-2]f[X-5]f[X-7]等都是已经得到结果的状态这个计算顺序就是OK的。
实际就是从小到大的计算方式偶有例外的情况。
例如我们算到F[12]的时候发现F[11]、F[10]、F[9]都已经算过了这种算法就是对的。而开始算F[27]的时候发现F[26]还没有算这样的顺序就是错的。
很显然这样的情况下写一个for循环就够了。
回到这道题采用动态规划的算法每一步只尝试三种硬币一共进行了27步。算法时间复杂度即需要进行的步数为27*3。
与递归相比没有任何重复计算。
本文的题目来源LeetCode - Medium - 322. Coin Change
代码如下
public class CoinChange {public int coinChange(int[] coins, int amount) {int[] f new int[amount 1];Arrays.fill(f, Integer.MAX_VALUE);f[0] 0;for (int i 1; i amount; i) {//如果通过放这个硬币能够达到数量ifor(int coin : coins) {if (i coin f[i - coin] ! Integer.MAX_VALUE)// 获得i的数量的硬币数就可能是获得i-A[j]重量硬币数的方案1// 拿这个方案数量与原本的方案数打擂台取最小值就行f[i] Math.min(f[i - coin] 1, f[i]);}}if (f[amount] Integer.MAX_VALUE) {return -1;}return f[amount];}
}总结
这是求最值问题用动态规划方式求解。案例最少硬币组合进入求解过程先确定问题状态 提炼最后一步最优策略中使用的最后一枚硬币aK子问题转化最少的硬币拼出更小的面值X-aK 构建转移方程f[X] min{f[X-2]1, f[X-5]1, f[X-7]1}设置初始条件和边界情况f[0] 0, 如果不能拼出Yf[Y]正无穷确定计算顺序并计算求解f[0], f[1], f[2],…
