例：
有面值1，3，5分的三种硬币，现在给出一个价值C，问组成价值C最少需要几枚硬币?

递归实现

  1. public class Corn {
  2.     public static void main(String[] args) {
  3.         int[] arr = {1, 3, 5};
  4.         int c = 16;
  5.         int num = func (arr, c);
  6.         System.out.println ("num：" + num);
  7.         System.out.println ("number: " + number);
  8.     }
  10.     static int number = 0;//记录递归的次数
  11.     private static int func(int[] arr, int c) {
  12.         if (c == 0) {
  13.             return 0;
  14.         }
  15.         number++;
  16.         if (c == 1 || c == 3 || c == 5) {
  17.             return 1;
  18.         } else {
  19.             if (c < 3) {
  20.                 return 1 + func (arr, c - 1);
  21.             } else if (c < 5) {
  22.                 int n1 = 1 + func (arr, c - 1);
  23.                 int n2 = 1 + func (arr, c - 3);
  24.                 return Math.min (n1, n2);
  25.             } else {
  26.                 int n1 = 1 + func (arr, c - 1);
  27.                 int n2 = 1 + func (arr, c - 3);
  28.                 int n3 = 1 + func (arr, c - 5);
  29.                 return Math.min (Math.min (n1, n2), n3);
  30.             }
  31.         }
  32.     }
  33. }

递归+打表

import java.util.Arrays;

public class Corn2 {
    public static void main(String[] args) {
        int[] arr = {1,3,5};
        int c = 15;
        int[] dp = new int[c+1];//记录组成价值i所需要的最少的硬币的数量
        Arrays.fill(dp, -1);
        int num = func(arr,c,dp);
        System.out.println ("num：" + num);
        System.out.println ("number" + number);
    }

    /**
     * arr数组放的是硬币，c是指定的价值，返回价值c最少需要的硬币的数量
     * @param arr
     * @param c
     */
    static int number = 0;//计算递归的次数
    private static int func(int[] arr,  int c,int[] dp) {
        if(dp[c] != -1){
            return dp[c];
        }
        number++;
        if(c == 0){
            dp[c] = 0;
            return 0;
        }
        if(c == 1 || c == 3 || c == 5){
            dp[c] = 1;
            return 1;
        }else {
            if(c < 3){
                dp[c] = 1 + func (arr,c-1,dp);
            }else if(c < 5){
                int n1 = 1 + func (arr,c-1,dp);
                int n2 = 1 + func (arr,c-3,dp);
                dp[c] = Math.min (n1,n2);
            }else{
                int n1 = 1 + func (arr,c-1,dp);
                int n2 = 1 + func (arr,c-3,dp);
                int n3 = 1 + func (arr,c-5,dp);
                dp[c] = Math.min (Math.min (n1,n2),n3);
            }
            return dp[c];
        }
    }
}

递推实现

dp[i] = min{1 + dp[i-1], 1 + dp[i-3], 1 + dp[i-5]}
dp[i] = min{1 + dp[i-v[j]]} i >= v[j]

import java.util.Arrays;

public class Corn2 {
    public static void main(String[] args) {
        int[] v = {1, 3, 5};
        int c = 16;
        int number = 0;
        int[] dp = new int[c + 1];
        for (int i = 1; i <= c; i++) {
            dp[i] = i;
            for (int j = 0; j < v.length; j++) {
                number++;
                if (i >= v[j] && 1 + dp[i - v[j]] < dp[i]) {
                    dp[i] = 1 + dp[i - v[j]];
                }
            }
        }
        System.out.println ("num：" + dp[c]);
        System.out.println ("number：" + number);
    }
}