解题思路:
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("><"); } } }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:1011 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:2485 |
C语言训练-计算:t=1-1/(2*2)-1/(3*3)-...-1/(m*m) (C语言代码)浏览:796 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:987 |
WU-拆分位数 (C++代码)浏览:815 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:588 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:1962 |
sizeof的大作用 (C语言代码)浏览:1126 |
局部变量作函数返回值的问题浏览:1020 |
数组输出 (C语言代码)浏览:745 |