首页 > 试题广场 >

换零钱

[编程题]换零钱

热度指数：5968 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有一个数组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

算法知识视频讲解

潇湘缘

import java.util.*;

public class Exchange {
    public int countWays(int[] changes, int n, int x) {
        // write code here
        //dp[i][j]表示使用changes[0~i]的钱币组成金额j的方法数
        int[][] dp=new int[n][x+1];
        //第一列全为1，因为组成0元就只有一种方法
        for(int i=0;i<n;i++)
            dp[i][0]=1;
        //第一行只有changes[0]的整数倍的金额才能有1种方法
        for(int j=0;j*changes[0]<=x;j++){
            dp[0][j*changes[0]]=1;
        }
        //从位置(1,1)开始遍历
        for(int i=1;i<n;i++){
            for(int j=1;j<=x;j++){
                //关键：使用0~i的钱币组成j-changes[i]金额的方法数+使用0~i-1钱币组成j的方法数
                dp[i][j]=dp[i-1][j]+(j-changes[i]>=0?dp[i][j-changes[i]]:0);
            }
        }
        
        return dp[n-1][x];
    }
}

发表于 2016-04-01 15:39:01 回复(7)

Java

JustYoung

import java.util.*;

public class Exchange {
    public int countWays(int[] changes, int n, int x) {
        // write code here
        int[] dp = new int[x + 1];
		dp[0] = 1;
		for (int change : changes) {
			for (int i = 0; i + change <= x; ++i) {
				dp[i + change] += dp[i];
			}
		}
		return dp[x];
    }
}

发表于 2016-09-05 23:24:14 回复(5)

orgcheng

对于找零问题有两个版本，一个是求找零后零钱的数量最少；另一个就是本题，求找零的方案数。

求解思路：
使用0个｛5｝时，求解子问题 X - 0 * 5 在｛10，25，1｝的方案数
使用1个｛5｝时，求解子问题 X - 1 * 5 在｛10，25，1｝的方案数
使用2个｛5｝时，求解子问题 X - 2 * 5 在｛10，25，1｝的方案数
……
把上面的方案是加起来就是所求的结果了，但是注意边界: 对 0 找零的方案数为 1。

使用递归求解比较简单，但是效率不高，因为会重复求解。

如果考虑使用迭代，需要申请辅助空间，存储计算的值。
而且还要重新需找求解过程，比较纠结。。。。。。我找了老半天，而且也不好解释，
关键是理解递归的过程。
下面是代码：

import java.util.*;

public class Exchange {
	public int countWays(int[] changes, int n, int x) {
		// 方法一：递归
		// return recursion(changes,0,n-1,x);

		// 方法二：迭代
		int[] arr = new int[x + 1];
		arr[0] = 1;

		int i = 0, j = 0;
		for (i = 0; i < n; ++i) {
			for (j = 0; j+changes[i] <= x; j++) {
				arr[j+changes[i]]+=arr[j];
			}
		}
		return arr[x];
	}

	public int recursion(int[] changes, int begin, int end, int target) {
		// 边界条件
		if (target == 0)
			return 1;
		if (begin > end || target < 0)
			return 0;

		int count = 0;
		int times = 0;

		// 找零的过程中使用了times次changes[begin]
		// 在后续的找零中，不再使用changes[begin]
		while (times * changes[begin] <= target) {
			count += recursion(changes, begin + 1, end, target - times * changes[begin]);
			++times;
		}
		return count;
	}
}

编辑于 2015-08-10 18:01:34 回复(7)

夕一啊

可以用一维的dp数组解决，最后dp[j]表示凑成j的方案数。

过程如下图，dp[j+changes[i]] += dp[j]; （j从0到14i表示第几列，change[i]表示加入的零钱）

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        int dp[x+1]; 
        for(int i =0;i<=x;i++)
            dp[i] = 0;
        dp[0] = 1;
        for(int i =0;i<n;i++)
            for(int j = 0;j+changes[i]<=x;j++)
                dp[j+changes[i]] += dp[j];
        return dp[x];
    }
};

编辑于 2017-06-28 21:40:26 回复(1)

牛客703246号

# -*- coding:utf-8 -*-
#project euler第31题目
class Exchange:
    def countWays(self, changes, n, x):
        ways = [1]+[0]*x
        for coin in changes:
           for i in range(coin, x+1):
               ways[i] += ways[i-coin]
        return ways[x]

编辑于 2016-05-15 09:17:52 回复(3)

大漠刀客

参考http://www.xuebuyuan.com/2119255.html

方法二中dp[ i ] [ j ]表示i元用零钱changes[0~j-1]来找，j=0表示没有可用的找零钱币。

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        // write code here
        int dp[ x+1 ] ;
        int i,j ;
        
        for( i=1; i<=x; i++ )
           dp[i] = 0 ;
        
        dp[ 0 ] = 1 ;//0元钱找零全部不选，所以方案数为1 
        
        for( i=0; i<n; i++ )//dp[j]=dp[j](不选changes[i])+dp[ j-changes[i] ](选择一个changes[i])
            for( j=changes[i]; j<=x; j++ )
              dp[ j ] = dp[j] + dp[ j-changes[i] ] ;
        
        return dp[ x ] ;
        
    }
};

class Exchange {

public:

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元钱，都不选

for( i=1; i<=x; i++ )

dp[i][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 ] ;

}

};

发表于 2016-05-02 10:00:21 回复(0)

mysterioussuperstar

假设输入是1,5,10,25,50 的情况

根据动态规划的思想，我们生成一个数组brr保存支付方式种类数，长度设定为x+1,。首先计算只有1分硬币的情况，此时无论n是多少，支付方式都只有一种并记录在数组brr中；然后，只有1分和5分硬币的情况，此时从5分开始计算（小于5分就不能用5分表示），于是brr[ j ] = brr[ j ]+brr[ j-5 ] ，等号左边brr[ j ] 表示 j 分钱的支付方式种类数，等号右边 brr[ j ] 表示只有1分硬币的时候的支付方式种类数而brr[ j-5] 表示，在j-5分钱的支付方式种类数已知的情况下，加上5分钱就可以等于j 分钱了。当硬币面值增大增多时，也是如此推导。

说的简单点就是可以用 arr[] = {1, 5, 10, 25, 50}来表示硬币的面值。 brr[10001]来存储总共的支付方式种类。
而 j 分钱的支付方式种类数就是等于，在brr[ j - arr[ i ] ] (i = 0~ 4) 的种类数，加上arr[ i ] 面值的硬币或者不加arr[ i ] 面值的硬币这两种情况，
即有递推公式 brr[ j ] = brr[ j ]+brr[ j - arr[ i ] ]

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        // write code here
        vector<int> brr(x+1,0);
        brr[0]=1;
        for(int i=0;i<n;++i)
        {
            for(int j=changes[i];j<x+1;++j)
            {
                brr[j]+=brr[j-changes[i]];
            }
        }
        
        return brr[x];
    }
};

发表于 2020-05-02 21:34:01 回复(0)

万叶飞花

// 暴力递归
public int countWays1(int[] changes, int n, int x) {
    if (x == 0) {
        return 1;
    } else if (n == 0) {
        return 0;
    }
    int res = countWays1(changes, n - 1, x);
    if (x >= changes[n - 1]) {
        for (int k = 1; k <= x / changes[n - 1]; k++) {
            res += countWays1(changes, n - 1, x - k * changes[n - 1]);
        }
    }
    return res;
}

// 动态规划
public int countWays2(int[] changes, int n, int x) {
    int[][] dp = new int[n + 1][x + 1];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= x; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= changes[i - 1]) {
                for (int k = 1; k <= j / changes[i - 1]; k++) {
                    dp[i][j] += dp[i - 1][j - k * changes[i - 1]];
                }
            }
        }
    }
    return dp[n][x];
}

// 动态规划的空间优化
public int countWays3(int[] changes, int n, int x) {
    int[] dp = new int[x + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = x; j >= 1; j--) {
            if (j >= changes[i - 1]) {
                for (int k = 1; k <= j / changes[i - 1]; k++) {
                    dp[j] += dp[j - k * changes[i - 1]];
                }
            }
        }
    }
    return dp[x];
}

发表于 2019-02-26 14:10:54 回复(0)

yellow2dong

public static int countWays(int[] changes, int n, int x) { // write code here  int[] memo = new int[x + 1];   memo[0] = 1;  for (int i = 0; i < n; i++) { for (int j = changes[i]; j <= x; j++) {
            memo[j] += memo[j - changes[i]];  }
    } return memo[x]; }

发表于 2018-09-02 16:05:51 回复(0)

讲道理的牛肉丸顶呱呱

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        // write code here
        vector<long> dp(x+1,0);
        dp[0]=1;
        for(int i=0;i<n;i++)
            for(int j=1;j<=x;j++)
                if(j>=changes[i])
                    dp[j]+=dp[j-changes[i]];
        return dp[x];
    }
};

发表于 2018-01-18 13:51:11 回复(0)

C/C++

nbgao

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        int dp[n][x+1];
        memset(dp,0,sizeof(dp));
        
        for(int i=0;i<n;i++)
            dp[i][0] = 1;
        for(int j=0;j*changes[0]<=x;j++)
            dp[0][j*changes[0]] = 1;
        for(int i=1;i<n;i++)
            for(int j=1;j<=x;j++)
            {
                if(j - changes[i] >= 0)
                    dp[i][j] = dp[i-1][j] + dp[i][j-changes[i]];
                else
                    dp[i][j] = dp[i-1][j];             }                      return dp[n-1][x];
    }
};

发表于 2017-10-20 00:51:14 回复(0)

Java

呜呜呜

//使用动态规划
import java.util.*;

public class Exchange {
    private int[][] map;

    private int[] changes;

    private int dp(int x, int y) {    //使用前x种货币组成y元的方法数
        if (x < 0 || y < 0) return 0;
        if (map[x][y] != 0) return map[x][y];    //将数据保存在数组中，避免重复递归
        if (y == 0) {
            map[x][y] = 1;
            return 1;        //组成0元的方法数为1
        } else {
            if (x == 0) {
                map[x][y] = 0;
                return 0;    //0种货币组成非0元的方法数为0
            }
        }
        if (x == 1) {
            if (y % changes[0] == 0) {
                map[x][y] = 1;
                return 1;    //只使用第一种货币，只有当y为此货币整数倍时方法数为1
            }
        }

        int k = y / changes[x - 1];    //能使用第x种货币的数量上限
        int res = 0;
        for (int i = 0; i <= k; i++) {
            //是否能使用i个编号为x的货币取决于能否使用x-1种货币组成y - i * changes[x - 1]元

            res += dp(x - 1, y - i * changes[x - 1]);
        }
        map[x][y] = res;
        return res;
    }


    public int countWays(int[] changes, int n, int x) {
        this.map = new int[n + 1][x + 1];
        this.changes = changes;
        return dp(n, x);
    }
}

编辑于 2017-01-11 23:13:08 回复(0)

fight灬奋斗

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        vector<int> vec(x+1,0);
        for(int i=0;i<n;i++){
            if(changes[i]<=x){
                vec[changes[i]]++;
                for(int j=1;j+changes[i]<=x;j++)
                	vec[j+changes[i]]+=vec[j];
            }
        }
        return vec[x];
    }
};

编辑于 2016-09-05 11:36:13 回复(0)

晓宇大美女~

动态规划

参考：http://www.xuebuyuan.com/2119255.html

代码：

    /**
	 * @param changes 零钱面值种类的数组
	 * @param n changes数组的大小
	 * @param x 要兑换的钱数
	 * @return 返回可以兑换的不同方式的数量
	 */
	public int countWays(int[] changes, int n, int x) {
		// 待兑换的金额是i，可用的范围是0-j-1
		// i = x,j = 0-n-1
		int[][] dp = new int[x + 1][n];
		// 当待兑换的金额是0的时候，都是只有一种
		for (int i = 0; i < n; i++)
			dp[0][i] = 1;
		// 第1列，待兑换的钱是i，因为只能用第一种零钱，所以只有当是第一种零钱的整数倍的时候，才有一种兑换方法
		for (int i = 1; i <= x; i++) {
			if (i % changes[0] == 0) {
				dp[i][0] = 1;
			}
		}
		//对于dp[i][j]，i是待兑换的钱数，j是changes[0-j]的钱币种类
		//dp[i][j] += dp[i][j-1],不用changes[j]这种钱
		//dp[i][j] += dp[i-changes[j]][j],用了一张changes[j]这种钱，剩下的待兑换的钱是i-changes[j]
		//只有以上两种可能
		for (int i = 1; i <= x; i++) {
			for (int j = 1; j < n; j++) {
				if (i - changes[j] >= 0)
					dp[i][j] += (dp[i][j-1] + dp[i - changes[j]][j]);
				else
					dp[i][j] += dp[i][j-1];
			}
		}
		return dp[x][n - 1];
	}

编辑于 2016-06-19 16:27:05 回复(0)

尼见

抄的第一个的，怎么想我也想不出来，我刷题刷的没信心了
	int[] arr = new int[x + 1];
		arr[0] = 1;

		int i = 0, j = 0;
		for (i = 0; i < n; ++i) {
			for (j = 0; j + changes[i] <= x; j++) {
				arr[j + changes[i]] += arr[j];
			}
		}
		System.out.println(arr[x]);
		return arr[x];

发表于 2016-05-26 15:34:18 回复(0)

waterbinbin


	classExchange {



	public:



	    intcountWays(vector<int> changes, intn, intx) {



	        // write code here



	        if(changes.size()==0|| changes.empty() || x<0)



	            return0;



	        vector<int> dp(x+1);



	        for(intj=0;changes[0]*j<=x;j++)



	            dp[changes[0]*j]=1;



	        for(inti=1;i<changes.size();i++)



	            for(intj=1;j<=x;j++)



	                dp[j]+=j-changes[i]>=0? dp[j-changes[i]]:0;



	        returndp[x];



	    }



	};

发表于 2015-10-05 09:49:32 回复(1)

攻城狮凌风

F(x)=F(x-5)+F(x-10)+F(x-25)+F(x-1);

发表于 2015-08-05 15:51:10 回复(2)

Python

lx的流星

# -*- coding:utf-8 -*-

class Exchange:
    def countWays(self,changes,n,x):
        # write code here
        dp=[]
        for i in range(n):
            dp.append([0]*(x+1))
        for i in range(n):
            dp[i][0]=1

        j=0
        while j*changes[0]<=x:
            dp[0][j*changes[0]]=1
            j+=1
        for i in range(1,n):
            for j in range(1,x+1):
                if j-changes[i]>=0:
                    dp[i][j]=dp[i-1][j]+dp[i][j-changes[i]]
                else:
                    dp[i][j]=dp[i-1][j]
        return dp[-1][-1]

发表于 2019-07-20 14:41:03 回复(0)

~似曾相识燕归来

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        if (changes.empty() || n <= 0 || x < 0) {
            return 0;
        }

        int rows = changes.size();
        int cols = x;

        vector<vector<int>> dp(rows + 1, vector<int>(cols + 1, 0));

        for (int i = 0; i <= rows; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (j - changes[i - 1] >= 0) {
                    dp[i][j] += dp[i][j - changes[i - 1]];
                }
                dp[i][j] += dp[i - 1][j];
            }
        }

        return dp[rows][cols];
    }
};

发表于 2019-06-08 15:31:36 回复(0)

人才库收割机

    public int countWays(int[] changes, int n, int x) {
        //初始化
        int[] dp = new int[x + 1];
        for (int i = 0; i < x + 1; i++)
            dp[i] = i % changes[changes.length - 1] == 0 ? 1 : 0;
        //动态更新
        for (int i = changes.length - 2; i >= 0; i--) {
            for (int j = 0; j < x + 1; j++) {
                    dp[j] += j >= changes[i] ? dp[j - changes[i]] : 0;
            }
        }
        return dp[x];
    }

发表于 2019-04-25 22:19:24 回复(0)