蓝桥杯2013年第四届真题-买不到的数目 新手代码，极易理解！！！

解题思路:dp[i]=0代表当钱数为i时没有办法得到

dp[i]=1代表可以得到

注意事项: 为啥dp[]后面存放数字全是1呢？

因为当dp连续出现>=最小面额的1时之后的dp数组全为1了

如 4 7

连续出现 18=7+7+4

               19=7+4+4+4

                20=4+4+4+4+4
                21=7+7+7

     之后就全可以取到了
参考代码:

import java.util.Scanner;

public class Main{
   static int dp[]=new int[1000000];
   public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       int m=sc.nextInt();
       int result = 0;

//面额只为n时的情况
       for(int i=0;i<dp.length;i++){
           if(i%n==0)
               dp[i]=1;
       }

//面额增加了一个m
       for(int i=0;i<dp.length;i++)
       {
           if(i>=m &&dp[i]==0)
                dp[i]=dp[i-m];
       }

//从后向前遍历
            for(int i=dp.length-1;i>=1;i--)
                if(dp[i]!=1)
                {
                   result=i;
                   break;
                }
//             for(int i=0;i<=25;i++)
//                 System.out.print(dp[i]+" ");
          System.out.println(result);      
   }
}