换零钱问题

换找零钱的方案数量

题目描述
有一个数组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+1 ][ n+1 ] ; int i,j ; for( j=0; j<=n; j++ ) dp[0][j] = 1 ;//0元钱,无论怎么换都是1 for( i=1; i<=x; i++ ) dp[i][0] = 0 ;//初始值，设置为0 for( i=0; i<=x; i++ ){ for( j=1; j<=n; j++ ){ if( (i-changes[j-1]) >= 0 )//如果可以用changes[j-1]找零 dp[ i ][ j ] = dp[i][j-1] + dp[ i-changes[j-1] ][j]; else dp[i][j] = dp[i][j-1]; } } 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+1 ] ; dp[0] = 1 ; for(int i=1; i <= x; ++i ) dp[i] = 0 ; for(int j= 1; j <= n; ++j ){ for(int i = 0; i <= x; ++i ){ if( (i-changes[j-1]) >= 0 )//如果可以用changes[j-1]找零 dp[ i ] = dp[i] + dp[ i-changes[j-1] ]; } } return dp[ x ] ; }

换零钱最少数量问题