换零钱

[编程题]换零钱

热度指数：6039 时间限制：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

算法知识视频讲解

Java

我是大牛膜拜吧小白

import java.util.*;

public class Exchange {
    public int countWays(int[] arr, int n,int aim) {
        if (arr == null || arr.length == 0 || aim < 0)
            return 0;
        int[][] dp = new int[arr.length][aim + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; arr[0] * j <= aim; j++) {
            dp[0][arr[0] * j] = 1;
        }
        int num = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                num = 0;
                for (int k = 0; j - arr[i] * k >= 0; k++) {
                    num += dp[i - 1][j - arr[i] * k];
                }
                dp[i][j] = num;
            }
        }
        return dp[arr.length - 1][aim];
    }
}

发表于 2018-02-14 00:29:34 回复(0)

Java

安徒生的谎言

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 i=0;i<changes.length;i++) {
            for(int j=1;j<=x;j++) {
                if(j>=changes[i]) {
                    dp[j]+=dp[j-changes[i]];
                }
            }
        }
        return dp[x];
    }
}

发表于 2018-01-27 11:07:50 回复(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)

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)