java 动态规划，递归实现 找零问题，币值最大化

package package1;

import java.util.Random;

class Coin {
   
    int monly;
    int num;

    public Coin(int monly, int num) {
   
        this.monly = monly;
        this.num = num;
    }
}

public class alg {
   

    public static int maxCoin(int[] n) {
   
        int a = 0, b = n[0], c = 0;
        for (int i = 1; i < n.length; i++) {
   
            c = Math.max(a + n[i], b);
            a = b;
            b = c;
        }
        return c;
    }

    /** * @param n 硬币 * @param isChoose 前一个数是否使用 * @param point 当前位置指针 * @param monly 钱 * @return 每个位置可以选，也可以不选。当选了的时候，后一个位置不能选，返回跳过。没选的时候后一个位置可选可不选，有两种情况，返回较大的数 */
    public static int recMaxCoin_(int[] n, boolean isChoose, int point, int monly) {
   
        if (point == n.length) {
   //到最后位置 数返回钱
            return monly;
        } else if (isChoose) {
   
            return recMaxCoin_(n, false, point + 1, monly);
        } else {
   
            return Math.max(recMaxCoin_(n, false, point + 1, monly), recMaxCoin_(n, true, point + 1, monly + n[point]));
        }
    }

    public static int recMaxCoin(int[] n) {
   
        return Math.max(recMaxCoin_(n, false, 1, 0), recMaxCoin_(n, true, 1, n[0]));
    }

    public static int minCoin(int[] n, int num) {
   
        Coin[] coin = new Coin[num + 1];
        coin[0] = new Coin(0, 0);
        for (int i = 1; i <= num; i++) {
   
            int j = 0, t = Integer.MAX_VALUE;
            while (j < n.length && n[j] <= i) {
   
                int temp = F(i - n[j], i, coin);
                if (temp == -1) {
   
                    System.out.println("找零问题出错!!! monly = " + (i - n[j]) + " 找不到对应最小硬币个数！");
                }
                t = Math.min(temp, t);
                j++;
            }
            coin[i] = new Coin(i, t + 1);
        }
        return coin[num].num;
    }

    public static int recMinCoin(int[] n, int num) {
   
        int min = num;
        for (int i : n) {
   
            if (i == num)
                return 1;
        }
        int mincoin = 0;
        for (int i : n) {
   
            if (i < num) {
   
                mincoin = 1 + recMinCoin(n, num - i);
                if (mincoin < min) {
   
                    min = mincoin;
                }
            }
        }
        return min;
    }

    public static int F(int monly, int maxIndex, Coin[] coins) {
   
        for (int i = 0; i < maxIndex; i++) {
   
            if (coins[i].monly == monly)
                return coins[i].num;
        }
        return -1;
    }

    public static int[] initArray(int len) {
   
        int[] n = new int[len];
        Random random = new Random();
        for (int i = 0; i < len; i++) {
   
            n[i] = random.nextInt(10);
        }
        return n;
    }

    public static void main(String[] args) {
   
        int[] n = initArray(40);
        int[] m = {
   1,2,5,10};
        int[] t = initArray(10);

        long a = System.currentTimeMillis();
        System.out.println("币值最大化 动态规划：" + maxCoin(n));
        long b = System.currentTimeMillis();
        System.out.println("耗时：" + (b - a) + "ms" + " 长度: " + n.length);

        a = System.currentTimeMillis();
        System.out.println("币值最大化 递归求解：" + recMaxCoin(n));
        b = System.currentTimeMillis();
        System.out.println("耗时：" + (b - a) + "ms" + " 长度: " + n.length);

        a = System.currentTimeMillis();
        System.out.println("找零 动态规划：" + minCoin(m, 40));
        b = System.currentTimeMillis();
        System.out.println("耗时：" + (b - a) + "ms" + " 长度: " + m.length + "零钱: 40");

        a = System.currentTimeMillis();
        System.out.println("找零 递归求解：" + recMinCoin(m, 40));
        b = System.currentTimeMillis();
        System.out.println("耗时：" + (b - a) + "ms" + " 长度: " + m.length+ "零钱: 40");
    }
}

结果