经典动态规划:背包问题-(LC322)

题目:

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

题解:

我们采用自下而上的方式进行思考。仍定义 F(i) 为组成金额 i 所需最少的硬币数量,假设在计算 F(i) 之前,我们已经计算出 F(0)−F(i−1) 的答案。

 c_j 代表的是第 j 枚硬币的面值,即我们枚举最后一枚硬币面额是 c_j ,那么需要从 i-c 这个金额的状态 F(i-c_j) 转移过来,再算上枚举的这枚硬币数量 1 的贡献,由于要硬币数量最少,所以 F(i) 为前面能转移过来的状态的最小值加上枚举的硬币数量 1 。


public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);//将数组dp全部填充为max值
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

来源:力扣(LeetCode)

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-06 17:06
黑龙江大学_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议