广州网站搭建多少钱,网站色彩搭配案例,南城网站优化公司,wordpress长文章不显示评论框题目#xff1a; 给你一个整数数组 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 思路 确定dp数组以及下标的含义 dp[j]凑足总额为j所需钱币的最少个数为dp[j] 确定递推公式 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]] 那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]考虑coins[i] 所以dp[j] 要取所有 dp[j - coins[i]] 1 中最小的。 递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]); dp数组如何初始化 首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0; 确定遍历顺序 如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。 在代码中if(dp[j - coins[i]] ! INT_MAX)表示如果如果dp[j - coins[i]]是初始值则跳过 说明没有可以凑成j-conis[i]的结果 最后先判断dp[amount]是否为初始化的最大值如果是说明没有结果 class Solution {
public:int track(vectorint coins, int amount) {vectorint dp(amount1,INT_MAX);dp[0] 0;for (int i 0; i coins.size();i) {for (int j coins[i]; j amount;j) {if (dp[j - coins[i]] ! INT_MAX) {dp[j] min(dp[j], dp[j - coins[i]] 1);}}}return dp[amount];}
};int main() {vectorint coins { 1,2,5 };int amount 11;Solution ss;coutss.track(coins,amount)endl;return 0;
}
