拼凑面额 解题报告 【动态规划】

拼凑面额 解题报告 【动态规划】

题目描述

  牛客OJ链接：拼凑面额
  给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0-10000的非负整数）的不同组合的个数。

输入描述:

  输入为一个数字N，即需要拼凑的面额。

输出描述:

输出也是一个数字，为组成N的组合个数。

示例1

输入

5

输出

2

思考

  一开始的思路是将大钱依次拆成小钱，如下图所示，将10元先拆成5元，接着5元再拆成1元。但是这种方法会导致重复，比如 1张5元和5张1元 与 5张1元和1张5元 的组成是一样的。没有想到去重的方法。

  接着经大牛提醒，得知这是一个线性丢番图方程。题目就转换成：
  已知：  $1\cdot x_1+5\cdot x_2+10\cdot x_3+20\cdot x_4+50\cdot x_5+100\cdot x_6=C;C$为要分解的价格
  求：  $x_1$ 至 $x_6$的非负整数解。
  虽然此方程有整数通解表示，但是求的是非负解，将是一个不等式组，解起来也并不方便。

动态规划求解

  最终还是看了讨论区的答案。动态规划的思路对照方程很容易理解，每个阶段都降低了方程的元数。
  比如：第一阶段：确定$x_6=x_6^{\prime }$，则 $1\cdot x_1+5\cdot x_2+10\cdot x_3+20\cdot x_4+50\cdot x_5=C-x_6^{\prime }=C_1$，此问题从6元方程转化成5元方程。第二阶段依此类推，从5元方程转化成4元方程。最终的一元方程$1\cdot x_1=C_6$ 总是有整数解的。得出状态转移方程:
$$dp[index][sum]=\sum _{s\in S_{index}}dp[index-1][sum-s]$$
  按照上面这个思路很容易写出备忘录式的递归代码：

#include <stdio.h>
#include <stdlib.h>int Prices[] = {1, 5, 10, 20, 50, 100};long long int Mem[6][10001]; //备忘录long long int GetCount(int sum, int index)
{if (Mem[index][sum] != -1)return Mem[index][sum];if (index == 0 || sum == 0) //递归出口return 1;long long int count = 0;int T = sum / Prices[index];for (int i = 0; i <= T; i++)count += GetCount(sum- Prices[index]*i, index - 1);Mem[index][sum] = count;return count;
}int main()
{int N = 0;scanf("%d", &N);for (int i = 0; i < 6; i++){for (int j = 0; j <= N; j++)Mem[i][j] = -1;}printf("%lld\n", GetCount(N, 5) );return 0;
}

  也可以按照状态转移方程写出递推形式：

#include <stdio.h>
#include <stdlib.h>int Prices[] = { 1, 5, 10, 20, 50, 100 };long long int DP[6][10001];int main()
{int i, j, k;int N = 0;scanf("%d", &N);for (j = 0; j <= N; j++)DP[0][j] = 1;for (i = 0; i < 6; i++)DP[i][0] = 1;int T;long long int count;for (i = 1; i < 6; i++){for (j = 1; j <= N; j++){T = j / Prices[i];count = 0;for (k = 0; k <= T; k++)count += DP[i - 1][j- Prices[i]*k];DP[i][j] = count;}}printf("%lld\n", DP[5][N]);return 0;
}

  还能进一步节省空间，由于每次都是用到上一状态的值，所以可以直接用一维数组保存状态，但需要注意状态的更新方式。从状态转移方程 $dp[index][sum]={\sum }_{s\in S_{index}}dp[index-1][sum-s]$ 可以看出，sum值都是依赖比它小的值。如果sum值从小到大更新，如图1所示，第一行蓝色代表上一次的状态数组；第二行红色部分为更新了的值；当出现第三行的情况，即之后用到了前面的值，但已经不是上一状态的值。当sum值从大到小更新则不会发生这样的情况。

图1 更新顺序

  代码为：

#include <stdio.h>
#include <stdlib.h>int Prices[] = { 1, 5, 10, 20, 50, 100 };long long int DP[10001];int main()
{int i, j, k;int N = 0;scanf("%d", &N);for (j = 0; j <= N; j++)DP[j] = 1;int T;long long int count;for (i = 1; i < 6; i++){for (j = N; j > 0; j--){T = j / Prices[i];count = 0;for (k = 0; k <= T; k++)count += DP[j- Prices[i]*k];DP[j] = count;}}printf("%lld\n", DP[N]);return 0;
}