淘先锋技术网

首页 1 2 3 4 5 6 7

换零钱问题

换找零钱的方案数量

题目描述
有一个数组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 ] ;
    }

换零钱最少数量问题