动态规划入门题目有N个硬币计算M钱用到最少硬币数量

动态规划

• 假如有3个硬币 2 . 5 . 7
• 现在需要27块钱 需要最少硬币数量

public class Test {
    public static void main(String[] args) {
         int a[]={2,5,7};
          int money=40;
        DynamicUtli dynamicUtli = new DynamicUtli();
        int utli = dynamicUtli.getUtli(a, money);
          System.out.println(utli);
          }
     }

public class DynamicUtli {
    // 硬币的种类数量   多少钱
    public  int  getUtli(int a[],int money){
 //定义一个数组  数组的长度为money
        //f[1] ...........f[money]
        int[]  f= new int[money+1];
        //初始化f[0]的值
        f[0]=0;
          //f[1] ...........f[money]
        for (int i = 0; i < f.length; i++) {
       //硬币的种类数量
            for (int j = 0; j < a.length; j++) {
                if (i>= a[j] && f[i-a[j]]!=Integer.MAX_VALUE) {
                 f[i]=Integer.MAX_VALUE;
         ```f[i] = Math.min(f[i - a[j]] + 1, f[i]);
}
}
}
    if (f[money]==Integer.MAX_VALUE){
            f[money]=-1;
        }
           return  f[money];
    }
    }