最简单的动态规划找零算法

package swTest;


/**
 * 动态规划学习
 * 1 找零问题 1,3,5 分的零钱，找11分钱，怎样个数最少
 * 采用动态规划的方法：
 *   @author samsung
 *   
 */
public class Test19 {
//	static    int[] change=new  int[]{1,3,5}; // 基础硬币数量
    static  int  conMum[] = new  int[99];  //对应的找零最小个数，保存最优状态
   
   static public void main(String[] arg){
	   conMum[0] = 0;
	   conMum[1] = 1;
	   conMum[2] = 2;
	   conMum[3] = 1;
	   conMum[4] = 2;
	   conMum[5] = 1;
	    //初始化数量
	 for(int i=6;i<99;i++){
		 concount(i); //规划求解
	 }
	 System.out.println(conMum[11]); //输出 11分就是 conMun[11];
   }
   
   /**
    * 函数 返回 面值 硬币的最小个数
    * @param con  面值
    * @param con1 硬币
    * @return
    */
   static void concount(int con){
		   conMum[con] = min(conMum[con-1]+1, conMum[con-3]+1, conMum[con-5]+1); 
		   //基本表达式就是这个
   }
   
   static int min(int a,int b,int c){
	    return Math.min(Math.min(a, b),c);
   }
}