[数据结构与算法]1021 货币系统（完全背包问题求方案数）

1. 问题描述：

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

输入格式

第一行，包含两个整数n和m。接下来n行，每行包含一个整数，表示一种货币的面值。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

n ≤ 15，m ≤ 3000

输入样例：

3 10
1
2
5

输出样例：

10
来源：https://www.acwing.com/problem/content/description/1023/

2. 思路分析：

分析题目可以知道我们需要选择一些面值的货币，求解使得这些货币最终恰好能够组成面值为m的货币的方案数目；每种面值的货币都是可以选择无限次的，所以属于经典的完全背包求解方案数目的问题，可以将货币看成是物品，构成面值为m可以看成背包的容量为m，与acwing1023买书的题目是一模一样的；完全背包问题属于动态规划中的经典问题，对于动态规划的问题主要有两个步骤：① 状态表示 ② 状态计算；我们一开始可以定义一个二维数组，其中dp[i][j]表示前i个物品中背包容量恰好为j的方案数目，对于背包容量"恰好"的题目我们在初始化的时候是将第一个状态值置为1，例如在一维数组的时候一般是dp[0] = 1；完全背包问题的二维状态转移方程为dp[i][j] = dp[i - 1][j] + dp[i][j - v]，其实我们可以将二维数组优化为一维数组，优化的过程其实一个等价变形的过程，可以发现状态转移方程中的dp[i - 1][j]为上一层循环对应的状态值，dp[i][j - v]为当前这一层循环对应的状态值，优化为一维之后状态转移方程为dp[j] += dp[j - v]，一开始进入循环的时候dp[j]属于上一层循环对应的状态值，而dp[j - v]小于j所以在遍历到j的时候j - v的状态已经在当前这一层循环计算过了所以dp[j - v]为当前这一层循环对应的状态值，恰好满足顺序遍历的要求，所以对于完全背包问题来说直接去掉第一维即可完成等价变形（对于一维的零一背包则需要逆序遍历才可以完成等价变形）。

3. 代码如下：

if __name__ == '__main__':
    n, m = map(int, input().split())
    dp = [0] * (m + 1)
    dp[0] = 1
    for i in range(n):
        v = int(input())
        # 逆序枚举体积
        for j in range(v, m + 1):
            dp[j] += dp[j - v]
    print(dp[m])