首页 > 编程语言 >算法学习day45动态规划part07-322、279

算法学习day45动态规划part07-322、279

时间:2023-06-05 23:57:40浏览次数:41  
标签:硬币 int coins part07 322 279 dp

package LeetCode.DPpart07;
/**
 * 322. 零钱兑换
 * 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回-1 。
 * 你可以认为每种硬币的数量是无限的。
 * */

public class CoinChange_322 {
    public static int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        for (int j = 0; j < dp.length; j++) {
            dp[j] = max;
        }
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            //正序遍历:完全背包每个硬币可以选择多次
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时,该位才有选择的必要
                if (dp[j - coins[i]] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }

}
package LeetCode.DPpart07;
/**
 * 279. 完全平方数
 * 给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
 * 完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
 * 示例:
 * 输入:n = 12
 * 输出:3
 * 解释:12 = 4 + 4 + 4
 */

public class PerfectSquares_279 {
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        //初始化
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
        //当和为0时,组合的个数为0
        dp[0] = 0;
        // 遍历物品
        for (int i = 1; i * i <= n; i++) {
            // 遍历背包
            for (int j = i * i; j <= n; j++) {
                if (dp[j - i * i] != max) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }

}

 

标签:硬币,int,coins,part07,322,279,dp
From: https://www.cnblogs.com/lipinbigdata/p/17459328.html

相关文章

  • COMPX322-23A: 管理应用
    COMPX322-23A:AssignmentFourDueDate:FridayJune9tht,5pmLibrariesandFrameworks:ProjectManagementApplicationForthiscourseworkyouarerequiredtobuildaprojectmanagementapplicationwhichallowsuserstomanagetheirprojects.Youwilluse:•......
  • 322.零钱兑换
    其中,dp[i][j]表示使用前i个硬币可以凑出总价值为j的钱数的最小硬币数,初始化时将dp[0][i]的值设为无穷大,因为凑出总价值为0的钱数不需要任何硬币。在状态转移方程中,如果j<coins[i-1],则不能选当前硬币,此时dp[i][j]=dp[i-1][j];否则,可以选当前硬币,dp[i][j]=dp[i][j-coins......
  • 20180315~20180322每天复习
    MPUSH架构图: 系统调用关系图: mpush目前支持如下消息类型 publicenumCommand{HEARTBEAT(1),//心跳HANDSHAKE(2),//握手LOGIN(3),LOGOUT(4),BIND(5),//绑定用户UNBIND(6),//解绑用户......
  • 322. 零钱兑换
    给你一个整数数组coins,表示不同面额的硬币;以及一个整数amount,表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回-1。你可以认为每种硬币的数量是无限的。输入:coins=[1,2,5],amount=11输出:3解释:11=5+......
  • 代码随想录算法训练营第21天 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中
     第六章 二叉树part07今日内容    详细布置   530.二叉搜索树的最小绝对差  需要领悟一下二叉树遍历上双指针操作,优先掌握递归 题目链接/文章讲解:视频讲解:  501.二叉搜索树中的众数  和 530差不多双指针思路,不过 这里涉及到一个很巧妙的代码......
  • hdu 2795(线段树)
    解题思路:这道题很难想到是用线段树,确实转化的很巧妙实际上,我们只需要利用线段树(记录1-h)维护哪个位置的剩余空间最大即可,即1,2,......,h是线段树的叶子节点,我们每次要找的就是叶子节点的剩余空间的最大值,只要能够想到这里就很容易啦。。另外如果h>n的话,就令h=n,否则就是类似于位置多......
  • 322. Coin Change刷题笔记
    用自底向上的dp算法classSolution:defcoinChange(self,coins:List[int],amount:int)->int:dp=[0]+[float('inf')]*amountforiinrange(1,amount+1):forcoinincoins:ifi-coin>=0:......
  • [abc279 G] At Most 2 Colors
    G-AtMost2Colors(atcoder.jp)重点讲解方法三,因为方法三是蒟蒻都能想出来的方法一和方法二都可以借助方法三的思想推出方法一这是最简单的设置状态的方法,\(dp[i]\)表示前\(i\)个的方案数,然后分类若\([i-k+1,i-1]\)有两种颜色那么第\(i\)位的取值肯定时这两种颜色中......
  • day45| 70+322+279
    70.爬楼梯 题目简述:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 思路:1.要想爬到第n阶,必须先上第n-1阶或者n-2阶2.利用动态规划,定义初始条件dp[0]=1,dp[1]=23.有dp[i]=dp[i-1]+dp[i-2],其中i......
  • 实验十 7279阵列式键盘实验
    实验十7279阵列式键盘实验实验目的1、掌握八段数码管硬件线路原理,掌握用HD7279A芯片实现显示的编程方法。2、熟悉键盘的工作原理,掌握用HD7279A芯片实现键盘扫描程序设计方法。实验内容HD7279A是一片具有串行接口的,可同时驱动8位共阴极数码管(或64只独立LED)的智能显示驱动芯......