换零钱问题
换找零钱的方案数量
题目描述
有一个数组changes，changes中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，对于一个给定值x，请设计一个高效算法，计算组成这个值的方案数。
给定一个int数组changes，代表所以零钱，同时给定它的大小n，另外给定一个正整数x，请返回组成x的方案数，保证n小于等于100且x小于等于10000。测试样例：
[5,10,25,1],4,15
返回：6
测试样例：
[5,10,25,1],4,0
返回：1
方法一：
这个题目的毫无疑问是用动态规划来解决的，重要的是状态的定义以及状态转移方程。其实这是一个类似组合数学的问题，对于m元钱，用n种面值的零钱来换，则我们把问题分成两种情况：
- 不用最后一种面值的零钱换(只用前n-1种面值的货币换零钱)有多少种解决方案，即：C(m,n-1);
- 使用最后一种面值的零钱换，那么换取的钱变成了m-changes[n] ，确保第n种面值至少用到一次，则剩下的金额还是用n 种面值来换，即：C(m-cahnges[n],n)；
- C(m,n) = C(m,n-1) + C(m-changes[n],n)
最终C(i,n) = C(i,n-1) + C(i-changes[n],n)，由此可以看到，这个问题被分解成为了两个子问题，一个在货币数量上规模减小，一个在金额上规模减小，这就是这个问题的地推关系式，只需要由地向上使用迭代的方式实现即可。
- 状态的定义：使用dp[i][j]表示使用前j种面值的货币来换i元钱时可行的方案数量；
- 状态转移方程：dp[i][j] = dp[i][j-1] + dp[i-changes[j]][j]，( 0 <=i < m+1, 0 <= j < j+1 );
- 注意边界条件 ，i-changes[j] >=0,时才成立；
- dp 是一个m+1行，n+1列的二维表，第一列和第一行都是确定的初始值。
- 时间和空间的复杂度都是O(m*n);
int countWays(vector<int> changes, int n, int x) {
// write code here
int dp[ x+ ][ n+ ] ;
int i,j ;
for( j=; j<=n; j++ )
dp[][j] = ;//0元钱,无论怎么换都是1
for( i=; i<=x; i++ )
dp[i][] = ;//初始值，设置为0
for( i=; i<=x; i++ ){
for( j=; j<=n; j++ ){
if( (i-changes[j-]) >= )//如果可以用changes[j-1]找零
dp[ i ][ j ] = dp[i][j-] + dp[ i-changes[j-] ][j];
else
dp[i][j] = dp[i][j-];
}
}
return dp[ x ][ n ] ;
}
- 整个过程用表列出来如下：
- 两个箭头交汇的地方表示相加，最后一列就是对应的x元钱用n中面值货币换零钱的方案数量。
- 优化：如果只用最后一列来存储结果则dp[x+1]即可。这个时候当计算到底i行的时候，dp[0]~dp[i-1]已经存储了对应x的最终的结果，但是在每一行的求解过程中需要用到上面某行的中间值(同列)，因此不能简单的只降低dp维度,这要求dp[0]~dp[i-1]还保存相应的中间值，则只能交换循环的内外层，循环在表上填充值先下后右，然后将dp降维度。
方法二：
- 经过优化后空间复杂度为O(x);
int countWays(vector<int> changes, int n, int x) {
// write code here
int dp[ x+ ] ;
dp[] = ;
for(int i=; i <= x; ++i )
dp[i] = ;
for(int j= ; j <= n; ++j ){
for(int i = ; i <= x; ++i ){
if( (i-changes[j-]) >= )//如果可以用changes[j-1]找零
dp[ i ] = dp[i] + dp[ i-changes[j-] ];
}
}
return dp[ x ] ;
}