//dp求count,max,min其实都很相似
洛谷的纸币问题2,3
纸币问题3,n种货币凑出w金额的凑法(1+2和2+1是一种选法),这就是与货币系统那道题一模一样
纸币问题2,n种货币凑出w金额的凑法(认为1+2和2+1是一种选法)
并且问题2,3中的每种货币都可以用无限次



先聊一聊纸币问题3,与货币系统一样

//1.本题与纸币2不同点在与1+5=6和5+1=6，前者认为是不同的，本题认为是相同的
//2,类似于完全背包，组合数一定是不重不漏的
//这里还可以做一个滚动数组的优化,实现一维dp

#include<iostream>
using namespace std;
int a[1010];
int f[1010][10010];//f[i][j]为前i个物品中选金额等于j的组合的数量
int n,w;
long long mod = 1e9+7;
int main()
{
    cin>>n>>w;
    for(int i=0;i<=n;i++)f[i][0]=1;//凑齐0金额也是一种方案
    //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<=w;j++)//枚举面值
    {
        int k;
        for(k=0;k*a[i]<=j;k++)//选k件第i中纸币
        {
            f[i][j]+=f[i-1][j-k*a[i]];
            f[i][j]=f[i][j]%mod;
        }
//优化如下：
        // if(a[i]<=j)
        // f[j]+=f[j-a[i]]%mod;
    }

    cout<<f[n][w];
    return 0;
}
`

接着聊纸币问题2,可以发现是先枚举金额(一元一元的凑),在枚举货币的。
为啥枚举顺序是这样的呢?
先循环金额，在循环1-n每个货币，闫氏dp分析法,相当于把每个钱币都试着放在最后一个位置，每个钱币都放在最后，就是排列
样例:   2 6
        1 5
    1,5// 钱币5被放在最后的排列
    5,1// 钱币1被放在最后的排列
    //1+5=5+1=6

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
const int V = 1010;
const int M =1e9+7;
int n,v;
int a[V];//a[i]表示第i种货币的面值
int f[N];//f[j]表示凑齐j元的方案数,f[j]=f[j-1,j-2,j-3,....j-k,.......1]
//j的前一个状态是凑齐k元
int cost;

int main()
{
    cin>>v>>n;
    for(int i=1;i<=v;i++)
    {
        cin>>a[i];
        //f[a[i]]=1;//初始化f[],凑齐a[i]元的方案最少有1,因为这种货币存在
    }

    //重复
    //f[3]包括了2 1,1 2, 1 1 1

    f[0]=1;
    for(int i=1;i<=n;i++)//面值,1元1元的凑
    {
        for(int j=1;j<=v;j++)//货币种类
        {
            if(i>=a[j])
             f[i]=(f[i]+f[i-a[j]])%M;
             //表示.........,a[j]这种排列
             .........凑成i-a[j]元的所有方案
             //闫氏dp分析法，最后一个不变，前面变,yyds
             //凑成i的方案,就是所有合法的货币都试着放在最后//一个位置的方案总和,这些方案中必然会有重合的部分//但这也是题目的要求，顺序不同即为不同
        }
        //f[i]=cost;
    }



    cout<<f[n]<<endl;
    return 0;
}
//所以这种对顺序有要求的dp我们以后要考虑是不是要以给出数组来作为第2维


//在纸币问题2的上面稍作改动,每一种货币只能用1次或者0次
//解法1
#include <iostream>
using namespace std;

const int MAX_N = 1005;
const int MAX_W = 10005;
const int MOD = 1e9 + 7;

int n, w, a[MAX_N], f[MAX_W][MAX_N];

int main() {
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    f[0][0] = 1;
    for (int i = 1; i <= w; i++) {
        for (int j = 1; j <= n; j++) {
            // 不使用第 j 个元素
            f[i][j] = f[i][j - 1];
            // 使用第 j 个元素
            if (i - a[j] >= 0) {
                f[i][j] = (f[i][j] + f[i - a[j]][j - 1]) % MOD;
            }
        }
    }

    cout << (f[w][n] % MOD) << endl;

    return 0;
}

//解法2
在这个特判条件下，确保了每个元素只能被选取一次，避免了重复计算.
当计算 f[4] 时，如果 4 - a[3] == a[3]（这里a[3]=2)
根据前面的理解，这里f[4]+=f[4-a[3],表示

凑成4-a[3](2)的所有排列---a[3]放在最后一个位置

//例如
    1 1,     2(a[3])
    2(a[3]), 2(a[3])
//凑成4-a[3](2)的所有排列中有一个2（a[3）的排列，那么a[3]在一个排列中就被选了2次
所以特判为i - a[j] != a[j]

#include <iostream>
using namespace std;

const int MAX_N = 1005;
const int MAX_W = 10005;
const int MOD = 1e9 + 7;

int n, w, a[MAX_N], f[MAX_W];

int main() {
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    f[0] = 1;
    for (int i = 1; i <= w; i++) {
        for (int j = 1; j <= n; j++) {
            if (i - a[j] >= 0 && i - a[j] != a[j]) {
                f[i] = (f[i] + f[i - a[j]]) % MOD;
            }
        }
    }

    cout << (f[w] % MOD) << endl;

    return 0;
}