1427: 蓝桥杯2013年第四届真题-买不到的数目 [动态规划] （Java代码）

解题思路:      动态规划模板题了，不过我的方式略微有一点不同，思路都差不多。

参考代码:

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] dp = new int[10000000];
        int[] ar = new int[2];
        ar[0] = sc.nextInt();
        ar[1] = sc.nextInt();
        dp[0] = 0;
        int max = 0;
        int count = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < ar.length; j++) {
                if (i >= ar[j] && dp[i - ar[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i - ar[j]] + 1, dp[i]);
                }
            }
            if (dp[i] == Integer.MAX_VALUE){
                max = i;
                count = 0;
            }else {
                count++;
                if (count > 1000){
                    System.out.println(max);
                    return;
                }
            }
        }
    }
}