动态规划一日一题-10-14-货币系统

货币系统

---

给定 V种货币（单位：元），每种货币使用的次数不限。

不同种类的货币，面值可能是相同的。

现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。

输入格式

第一行包含两个整数 V 和 N。

接下来的若干行，将一共输出 V 个整数，每个整数表示一种货币的面值。

输出格式

输出一个整数，表示所求总方案数。

数据范围

1≤V≤25
1≤N≤10000
答案保证在long long范围内。

输入样例：

3 10
1 2 5

输出样例：

10

---

好的，这一题是明显的dp问题，特征非常明显，以至于让我第一次看到，就想到了完全背包和整数划分两道题目，应该就是需要稍微数学归纳一下就可以找出来状态转移方程了。

还是老样子的思维模式：

状态表示：f[i] [j] 表示用前i个物品，正好凑出target的方案数

状态属性：种类

base case：f[i] [0] = 1 ;

状态转移：

f[i] [j] = f[i-1] [j] + f[i-1] [j-v[i]] + f[i-1] [j-2*v[i]] + ……..

f[i] [j-v[i]] = f[i-1] [j-v[i]] + f[i-1] [j-2*v[i]] + ……..

好的，合并一下，f[i] [j] = f[i-1] [j] + f[i] [j-v[i]] ;

好的，直接上代码，但是有一个关键点，此题是让你正好凑成target，所以要保证所有的状态都是由f[0] 转移过来的。

#include 

using namespace std ; 

const int N = 10010 ; 

long long f[N][N] ;

int a[N] ; 

int main()
{
    int n , target ; 
    cin >> n >> target ;
    
    for(int i = 1 ; i <= n ; ++ i)
    {
        cin >> a[i] ; 
    }
    
    for(int i = 1 ; i <= n ; ++ i)
        f[i][0] = 1 ; 
    
    for(int i = 1 ; i <= n ; ++ i)
    {
        for(int j = 1 ; j <= target ; ++ j)
        {
            f[i][j] = f[i-1][j] ; 
            if(j >= a[i])
            {
                f[i][j] += f[i][j-a[i]] ;
            }
        }
    }
    
    cout << f[n][target] << endl ; 
    
    return 0  ; 
}

好，同样的道理，可以同完全背包一样进行一维优化。

#include 

using namespace std ;

const int N = 100010 ; 

int a[N] ; 

long long f[N] ; 

int main()
{
    int n , m ; 
    
    cin >> n >> m ; 
    
    f[0] = 1 ; 
    for(int i = 1 ; i <= n ; ++ i)
    {
        cin >> a[i] ;  
    }
    
    for(int i = 1 ; i <= n ; ++ i)
    {
        for(int j = 1 ; j <= m ; ++ j)
        {
            if(j >= a[i])
            {
                f[j] += f[j-a[i]];
            }
        }
    }
    
    cout << f[m] << endl ; 
    
    return  0 ;  
}