网站目录 整理,自适应型网站建设服务电话,关键词排名网站,网页界面设计历史给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1 。
你可以认为每种硬币的数量是无限的。
示…给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1 输入coins [1, 2, 5], amount 11 输出3 解释11 5 5 1 示例 2 输入coins [2], amount 3 输出-1 示例 3 输入coins [1], amount 0 输出0 提示 1 c o i n s . l e n g t h 12 1 coins.length 12 1coins.length12 1 c o i n s [ i ] 2 31 − 1 1 coins[i] 2^{31} - 1 1coins[i]231−1 0 a m o u n t 1 0 4 0 amount 10^4 0amount104 思路动态规划
定义 f[i] 为组成金额 i 所需最少的硬币数量枚举 组成金额为 i 所需的硬币最后一个硬币 j如果最后一个金币是 j则当前硬币数量 f[i] f[i - coins[j]] 1所以有状态转移方程f[i] min(f[i], f[i - coins[j]] 1)
class Solution {
public:int f[10010];int coinChange(vectorint coins, int amount) {memset(f, 0x3f, sizeof f);f[0] 0;int n coins.size();for(int i 1; i amount; i){for(int j 0; j n; j){if(coins[j] i){f[i] min(f[i], f[i - coins[j]] 1);}}}return f[amount] 1e4 ? -1: f[amount];}
};
