[算法提高VIP]贪吃的大嘴

解题思路:

1.确认边界条件 第一行 第一列

题目要求是刚好满足美味度的最少吃发，

那么动态转移方程就是    当前物品美味度正好等于j  那么就是1

                                      当前物品美味度小于j 那么就是1+多余的吃法 和 上一个吃法 比小

                                      当前物品美味度大于j  那么就是继承上一个吃饭

     1    2    3    4    5    6    7    8    9    10    

4    0    0    0    1    0    0    0    0    0    0    

2    0    1    0    1    0    2    0    0    0    0    

2    0    1    0    1    0    2    0    3    0    0    

2    0    1    0    1    0    2    0    3    0    4    

参考代码:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class 贪吃的大嘴 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner scanner = new Scanner(System.in);
		int m = scanner.nextInt();// 满足美味度
		int n = scanner.nextInt();// 总类
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			int number = scanner.nextInt();//
			int a = scanner.nextInt();// 个数
			for (int j = 0; j < a; j++) {
				arrayList.add(number);
			}
		}
		// 刚好等于m
		// 第一行
		int[][] dp = new int[arrayList.size() + 1][m + 1];
		for (int[] is : dp) {
			Arrays.fill(is, Integer.MAX_VALUE-n);
		}
		for (int i = 1; i <= m; i++) {
			if (arrayList.get(0) == i) {
				dp[1][i] = 1;
			}
		}
		// 第一列
		for (int i = 1; i <= arrayList.size(); i++) {
			if (arrayList.get(i - 1) == 1) {
				dp[i][1] = 1;
			} else {
				dp[i][1] = dp[i - 1][1];
			}
		}

		// 状态转移方程
		for (int i = 2; i <= arrayList.size(); i++) {
			for (int j = 2; j <= m; j++) {
				int num=arrayList.get(i-1);
				if (num==j) {
					dp[i][j]=1;
				}
				else if(j>num) {
				  dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-num]+1 );
				}
				else {
					dp[i][j]=dp[i-1][j];
				}
			}

		}
		int sum=dp[arrayList.size()][m];
		if (sum<Integer.MAX_VALUE-n) {
			System.out.println(sum);
		}
		else {
			System.out.println("><");
		}
		

	}

}