leetcode【322-零钱兑换】思考、优化、改进

谁借莪１个温暖的怀抱￠ 2023-01-08 04:23 111阅读 0赞

leetcode【322-零钱兑换】思考、优化、改进  
 声 明 ： 该 系 列 是 我 的 随 笔 ， 会 记 录 一 些 刷 题 的 感 受 ， 思 路 。 文 章 难 免 有 错 误 或 语 句 不 够 严 谨 ， 欢 迎 指 正 。 \\color\{\#FF0000\}\{声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。 \} 声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。  
 如 果 读 者 关 于 这 道 题 有 其 他 疑 问 ， 也 欢 迎 在 评 论 区 和 我 讨 论 我 会 及 时 回 复 ， 互 相 进 步 ， 谢 谢 ！ \\color\{\#FF0000\}\{如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！\} 如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！  
    凑零钱问题当是动态规划最经典的问题之一，最近准备再复习一下这些基础问题（好久没敲代码手真的很生，很可怕）

int coinChange(vector<int>& coins, int amount) { 
    	vector<int> ans(amount+1,amount+1);
    	for(int i=0;i<amount+1;i++){ 
       	 if(i==0)
        	   ans[i] = 0;
       	 else
        	for(int j=0;j<coins.size();j++)
       	 if(i-coins[j]>=0)
            ans[i] = min(ans[i],ans[i-coins[j]]+1);
    	}  
    	return (ans[amount]==amount+1) ? -1:ans[amount];
    	}
    	执行用时：
    100 ms, 在所有 C++ 提交中击败了83.17%的用户
    内存消耗：13.7 MB, 在所有 C++ 提交中击败了82.95%的用户

状态转移方程这些应该没什么可说的，唯独需要注意的是初始值，一般会设为正无穷，我们知道16位机器补码最大正整数为65535，,32位机可以设置为0XFFFFFFFF。但上文中设置为amount+1也是一个常见的设置，因为硬币的额度最小值也是1，所以凑amount价值的硬币结果并不会大于amount的值。  
这题便不再多谈，因为网上的资料已经很详细了