首页 > 编程语言 >(算法)零钱兑换————<动态规划>

(算法)零钱兑换————<动态规划>

时间:2024-11-08 10:49:46浏览次数:3  
标签:初始化 硬币 int coins amount 零钱 算法 兑换 dp

1. 题⽬链接:322. 零钱兑换

2. 题⽬描述:

3. 解法(动态规划):

算法思路:

先将问题「转化」成我们熟悉的题型。

i. 在⼀些物品中「挑选」⼀些出来,然后在满⾜某个「限定条件」下,解决⼀些问题,⼤概率

是「背包」模型;

ii. 由于每⼀个物品都是⽆限多个的,因此是⼀个「完全背包」问题。

接下来的分析就是基于「完全背包」的⽅式来的。

1. 状态表⽰:

dp[i][j] 表⽰:从前 i 个硬币中挑选,总和正好等于 j ,所有的选法中,最少的硬币个

数。

2. 状态转移⽅程:

线性 dp 状态转移⽅程分析⽅式,⼀般都是根据「最后⼀步」的状况,来分情况讨论。但是最后⼀个物品能选很多个,因此我们的需要分很多情况:

        i. 选 0 个第 i 个硬币:此时相当于就是去前 i - 1 个硬币中挑选,总和正好等于 j 。此时最少的硬币个数为 dp[i - 1][j] ;

        ii. 选 1 个第 i 个硬币:此时相当于就是去前 i - 1 个硬币中挑选,总和正好等于 j -v[i] 。因为挑选了⼀个 i 硬币,此时最少的硬币个数为 dp[i - 1][j -coins[i]] + 1 ;

        iii. 选 2 个第 i 个硬币:此时相当于就是去前 i - 1 个硬币中挑选,总和正好等于 j- 2 * coins 。因为挑选了两个 i 硬币,此时最少的硬币个数为 dp[i - 1][j -2 * coins[i]] + 2 ;

        iv. ......

结合我们在完全背包⾥⾯的优化思路,我们最终得到的状态转移⽅程为:

dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。

这⾥教给⼤家⼀个技巧,就是相当于把第⼆种情况 dp[i - 1][j - coins[i]] + 1 ⾥⾯的 i - 1 变成 i 即可。

3. 初始化:

初始化第⼀⾏即可。

这⾥因为取 min ,所以我们可以把⽆效的地⽅设置成⽆穷⼤ (0x3f3f3f3f)

因为这⾥要求正好凑成总和为 j ,因此,需要把第⼀⾏除了第⼀个位置的元素,都设置成⽆穷⼤。

4. 填表顺序:

根据「状态转移⽅程」,我们仅需「从上往下」填表即可。

5. 返回值:

根据「状态表⽰」,返回 dp[n][V] 。但是要特判⼀下,因为有可能凑不到

 C++ 优化前的算法代码:

#define N 0x3f3f3f3f
class Solution 
{
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        //建表
        int m=coins.size(),n=amount;
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        //初始化
        for(int i=1;i<=n;i++)
        {
            dp[0][i]=N;
        }
        //填表
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                //不选
                dp[i][j]=dp[i-1][j];
                //选
                //因为完全背包此处判断的是dp表同一行的状态
                //使得dp[i][j]不存在时也会进入判断,故将选不到的状态定为极大值
                if(j-coins[i-1]>=0&&dp[i][j-coins[i-1]]!=N)
                {
                    dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1);
                }
            }
        }
        //返回值
        return  ((dp[m][n] == N) ? -1 : dp[m][n]);
    }
};

C++ 空间优化后的算法代码:

#define N 0x3f3f3f3f
class Solution 
{
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        //建表
        int m=coins.size(),n=amount;
        vector<int>dp(n+1);
        //初始化
        for(int i=1;i<=n;i++)
        {
            dp[i]=N;
        }
        //填表
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                //因为完全背包此处判断的是dp表同一行的状态
                //使得dp[i][j]不存在时也会进入判断,故将选不到的状态定为极大值
                if(j-coins[i-1]>=0&&dp[j-coins[i-1]]!=N)
                {
                    dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
                }
            }
        }
        //返回值
        return  ((dp[n] == N) ? -1 : dp[n]);
    }
};

Java 优化前算法代码:

class Solution
{
	public int coinChange(int[] coins, int amount)
	{
		// 1. 创建 dp 表
		// 2. 初始化
		// 3. 填表
		// 4. 返回值
		int n = coins.length, INF = 0x3f3f3f3f;
		int[][] dp = new int[n + 1][amount + 1];
		for (int j = 1; j <= amount; j++) dp[0][j] = INF;
		for (int i = 1; i <= n; i++)
			for (int j = 0; j <= amount; j++)
			{
				dp[i][j] = dp[i - 1][j];
				if (j >= coins[i - 1])
					dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
			}
		return dp[n][amount] >= INF ? -1 : dp[n][amount];
	}
}

Java 空间优化后的算法代码:

class Solution
{
	public int coinChange(int[] coins, int amount)
	{
		// 1. 创建 dp 表
		// 2. 初始化
		// 3. 填表
		// 4. 返回值
		int n = coins.length, INF = 0x3f3f3f3f;
		int[] dp = new int[amount + 1];
		for (int j = 1; j <= amount; j++) dp[j] = INF;
		for (int i = 1; i <= n; i++)
			for (int j = coins[i - 1]; j <= amount; j++)
				dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
		return dp[amount] >= INF ? -1 : dp[amount];
	}
}

标签:初始化,硬币,int,coins,amount,零钱,算法,兑换,dp
From: https://blog.csdn.net/2301_79580018/article/details/143613548

相关文章

  • 调度算法(二)
    调度算法(二)(1)前言比起早期的批处理操作系统来说,由于计算机造价大幅降低,因此之后出现的交互式操作系统(包括分时操作系统、实时操作系统等)更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。(比如U......
  • 调度算法(一)
    调度算法(一)(1)前言此处列举的三种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标,但是不关心“响应时间”,也并不区分任务的紧急程度,因此对于用户来说,交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统,当然,FCFS算法也常结合其他的算......
  • 人工智能图像算法:开启视觉新时代的钥匙
    一、引言在当今科技飞速发展的时代,人工智能已经成为了各个领域的热门话题。其中,人工智能图像算法作为人工智能领域的一个重要分支,正以其强大的功能和广泛的应用场景,改变着我们的生活和工作方式。本文将深入探讨人工智能图像算法的重要性以及其在各个领域的应用场景。二、人......
  • 基于遗传优化的SVD水印嵌入提取算法matlab仿真
    1.程序功能描述基于遗传优化的的SVD水印嵌入提取算法。对比遗传优化前后SVD水印提取性能,并分析不同干扰情况下水印提取效果。2.测试软件版本以及运行结果展示MATLAB2022a版本运行SVD GA优化SVD 性能对比: 3.核心程序%遍历遗传算法返回的各代最优个体(从......
  • FootyForecast足球数据预测软件——XGBoost算法实战
    足球数据分析——XGBoost算法实战基于上数据分析的AI足球大模型预测平台,感兴趣的可以下载。足球预测专家推荐链接:http://lcsjfx.com/FootyForecast/DownLoad随着足球数据的日益丰富,数据分析在足球领域的应用也越来越广泛。其中,XGBoost算法作为一种高效、强大的机器......
  • 【算法】动态规划
    一、算法概念动态规划算法是一种解决多阶段决策问题的方法。它将一个问题分解为多个子问题,并逐个求解子问题的最优解,最后得到原问题的最优解。二、基本思想动态规划算法的核心思想是通过存储中间结果来避免重复计算。在解决问题的过程中,会利用已经求解过的子问题的最优解......
  • 代码随想录算法训练营第九天|LeetCode151.翻转字符串里的单词、卡码网:55.右旋转字符串
    前言打卡代码随想录算法训练营第49期第九天︿( ̄︶ ̄)︿首先十分推荐学算法的同学可以先了解一下代码随想录,可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解,卡哥清晰易懂的算法教学让我直接果断关注,也十分有缘和第49期的训练营大家庭一起进步。今日题目LeetCode151翻转字......
  • 代码随想录算法训练营 day37 day38| 卡码网52.完全背包 518. 零钱兑换 II 377.
    学习资料:https://programmercarl.com/背包问题理论基础完全背包.html#算法公开课相比于01背包,完全背包中每个物品都可以无限次的放入组合:先遍历物品,再逆序遍历背包排列:先逆序遍历背包,再遍历物品学习记录卡码网52.携带研究资料(dp[i]代表当重量为i时的最大价值)点击查看代码n......
  • 大数据学习笔记 第5天 ZooKeeper 3.6.3安装部署 CAP原则 Paxos算法 ZAB协议详解
    ZooKeeper3.6.3重点CAP原则Paxos算法存储模型和监听机制一、集群与分布式集群:将一个任务部署在多个服务器,每个服务器都能独立完成该任务。分布式:将一个任务拆分成若干个子任务,由若干个服务器分别完成这些子任务,每个服务器只能完成某个特定的子任务。从概念上就可......
  • 算法每日双题精讲——双指针(移动零,复写零)
    ......