Last Order
0%

一个硬币凑齐数值的问题

发表于 更新于 分类于

晚上看到qq群里讨论一个算法题：
四个人分别有10000元 A只有1元的 B只有2元的 C只有5元的 D只有10元的

1.问现在要凑10000元 有多少方法 ？
2.假设投资额为10000，但最高出资的比例不能超过51%，问集资方案有多少种 ？

为了准备面试，第一次刷题，刷了四五天的leetcode，结果面试算法题写出来了，但还是挂了，有点迷茫睡了一觉，醒来刚好看到这个题目，顺便做一做把。因为自己完全不知道动态规划，只知道个名称，最后做出来花了很久。

思路的话第一时间想到的是leetcode上一个爬楼梯的题目，不过仔细算了下发现有点不太一样，一个是爬楼梯有顺序，二是爬楼梯只有1步和2步。

这里的话，如果我们用4种面值去凑11块钱，那么，D可能出0或者1张，如果出0张，那问题就变成了3种面值去凑11块钱，如果出1张，那么问题就变成了3种面值去凑1块钱，嗯，这是关键的部分，其他的可以类似的推算，比如4种面值去凑22块钱，那么D可能出0，1，2张，又变成3个3种面值去凑钱的问题，根据5块钱出0，1，2….等等张数的时候，3种面值去凑钱又可以变成2种面值去凑钱的问题，2种面值去凑钱的话，根据2块钱出0，1…张可以直接得出有多少种方法，比如2种面值凑3块钱，那么2块钱可以出0或者1张，有两种方法。2种面值凑4块钱，则是3种方法，因为2块钱可以出0，1，2三种，5块钱依然是3种方法。下面就是代码实现了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class Test {

    public static void main(String[] args) {
        System.out.println(get4n(10000));  // 1671170501
        System.out.println(get4n(10000, 5100));  //884304594
    }


   // 表示用4种(1,2,5,10)硬币计算凑齐n块钱有多少种方法,i表示出的10块钱的总额，例如
    // i==0的时候，就表示要用3种硬币凑齐所有的n块钱
    public static long get4n(int n) {
        long sum = 0;
        for (int i = 0; i <= n; i += 10) {
            sum += get3n(n - i);
        }
        return sum;
    }

    // 表示用3种(1,2,5)硬币计算凑齐n块钱有多少种方法
    private static long get3n(int n) {
        long sum = 0;
        for (int i = 0; i <= n; i += 5) {
            sum += get2n(n - i);
        }
        return sum;
    }

    // 表示用2种(1,2)硬币计算凑齐n块钱有多少种方法
    private static long get2n(int n) {
        return 1 + (n / 2);
    }

    // 出的10块钱的总额不得大于 maxPer
    public static long get4n(int n, int maxPer) {
        long sum = 0;
        for (int i = 0; i <= maxPer; i += 10) {
            sum += get3n(n - i, maxPer);
        }
        return sum;
    }

    // 出的5块钱的总额不得大于 maxPer
    private static long get3n(int n, int maxPer) {
        long sum = 0;
        for (int i = 0; i <= maxPer; i += 5) {
            sum += get2n(n - i, maxPer);
        }
        return sum;
    }

    private static long get2n(int n, int maxPer) {
        if (n < maxPer) {
            return 1 + (n / 2);
        } else {
            int bMax = maxPer / 2 - 1;
            int bMin = (n - maxPer) / 2 + 1;
            if (bMax < bMin) {
                return 0;
            }
            return bMax - bMin + 1;
        }
    }