硬币找零dp_硬币找零

亦凉 2023-03-05 07:28 11阅读 0赞

硬币找零dp

**Problem statement:**

**问题陈述：**

Given a value **N**, find the number of ways to make change for **N** cents, if we have infinite supply of each of **S = \{ S1, S2, .. , Sm\}** valued coins. The order of coins doesn't matter.

给定一个值**N** ，如果我们有无限个**S = \{S1，S2，..，Sm\}**值的硬币，则可以找到**N**分钱的兑换方法。 硬币的顺序无关紧要。

**Example:**

**例：**

Input:
        N = 4 
        S = {1, 2, 3} //infinite number of 1 cent, 2 cent, 3 cent coins
    
        Output:
        4
        {1,1,1,1} //four 1 cent coins
        {1,1,2} //two 1 cent coins, one 2 cent coins
        {2,2} //two 2 cent coins 
        {1,3} //one 1 cent and one 3 cent coins
        Thus total four ways (Order doesn’t matter)

**Solution**

**解**

Let's think of the solution. Let’s do it by hand first. An intuitive idea can be two checks whether the amount can be handled by the same valued coins.

让我们考虑一下解决方案。 让我们先手动操作。 一个直观的想法是两次检查是否可以用相同价值的硬币处理该金额。

Like 4 cent can be managed by four 1 cent coins.

像是4分钱，可以由4个1分钱硬币管理。

Same time can be managed by two 2 cent coins.

同一时间可以用两个2美分硬币来管理。

For the rest, we need to take different valued coins.

其余的，我们需要采用不同价值的硬币。

Now we can think of memorization. We can simply store the sub-amounts that can have been managed still.

现在我们可以想到记忆了。 我们可以简单地存储仍可以管理的子金额。

Like two 1 cent coin manage 2 cents. Thus 2 cent is our sub amount.

像两个1美分硬币一样管理2美分。 因此2美分是我们的子金额。

Now we pick two more 1 cent coins that will sum up to 4.

现在，我们再选择另外两个1分硬币，总计为4。

Else we can pick only one 2cent coin also summing up to 4.

否则，我们只能选择一枚2分硬币，总计为4分。

This memorized approach helps us to solve the problem.

这种记忆的方法有助于我们解决问题。

Let's revise the algorithm

让我们修改算法

**Pre-requisite:** **Coins** array, **amount**

**先决条件：** **硬币**阵列， **数量**

**Algorithm:**

**算法：**

1.  Create a DP table of size amount
            Table[amount+1]={0};
        2.  Base case table[0]=1
        3.  For each coins[i] from the coins array
                For j= 1: amount //j be the sub-amount
                    IF j>=coins[i] 
                        Table[j]=table[j]+table[j-coins[i]]
                    END IF
                END For
            END For
        4.  Return table[amount]
        Table[amount] refers to all possible way to make the amount

**Example with explanation:**

**带有说明的示例：**

We have pre added coin 0-cent as coin[0]=0
        For Coin index:  1 //coins[1]=1
    
        Sub amount:1
    
        Table status:
        1 | 1 | 0 | 0 | 0
    
    
        Sub amount:2
        Table status:
        1 | 1 | 1 | 0 | 0
    
        Sub amount:3
    
        1 | 1 | 1 | 1 | 0
        Sub amount:4
        1 | 1 | 1 | 1 | 1

This actually shows that by coin\[1\] all the sub-amounts can be managed only by one way, so if we continue this way for other coins we will get all the possible ways.

这实际上表明，通过coin \[1\]只能以一种方式管理所有子金额，因此，如果我们继续对其他硬币进行这种方式，我们将获得所有可能的方式。

**C++ implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    void findway(vector<int> a,int n,int amount){
        
    	int table[amount+1]; //DP table
    	memset(table,0,sizeof(table));
    	table[0]=1;
    	//j be the sub-amounts
    	for(int i=1;i<=n;i++){
        
    		for(int j=1;j<=amount;j++){
        
    		if(j>=a[i])
    			table[j]+=table[j-a[i]];
    		}
    	}
    	cout<<table[amount]<<endl; //final result
    }
    
    int main()
    {
        
    	int n,item,amount;
    
    	cout<<"Enter the number of coins\n";
    	scanf("%d",&n);
    	
    	cout<<"Enter value of coins\n";
    	vector<int> a; //coins array
    	//we pre add 0-cent coin as coins[0] 
    	//for sake of 1 indexing
    	a.push_back(0); 
    	
    	for(int j=0;j<n;j++){
        
    		scanf("%d",&item);
    		a.push_back(item);
    	}
    	
    	cout<<"Enter total amount\n";
    	cin>>amount;
    	cout<<"Number of ways to sum the amount is: ";
    	findway(a,n,amount); 
    	
    	return 0;
    }

**Output**

**输出量**

Enter the number of coins
    3
    Enter value of coins
    1 2 3
    Enter total amount
    4
    Number of ways to sum the amount is: 4

> 翻译自: [https://www.includehelp.com/icp/coin-change.aspx][https_www.includehelp.com_icp_coin-change.aspx]

硬币找零dp

[https_www.includehelp.com_icp_coin-change.aspx]: https://www.includehelp.com/icp/coin-change.aspx