1 public class DynamicPlan {
 2     // 100 个人 挖 5 个矿
 3     private static int peopleCount=100;
 4     private static int poolCount=5;
 5     // 挖每个矿时需要的人数
 6     private static int[] peopleNeed={77,22,29,50,99};
 7     // 每个矿可以挖出来的金币数
 8     private static int[] goldEach={92,22,87,46,90};
 9     // 挖矿中间过程的备忘
10     private static Integer[][] backup=new Integer[100][5];
11     public static void main(String[] args) {
12         for(int i=0;i<peopleCount;i++) {
13             for(int j=0;j<poolCount;j++) {
14                 backup[i][j]=-1;
15             }
16         }
17         int max=getMaxGold(peopleCount-1,poolCount-1);
18         System.out.println(max);
19     }
20     
21     public static int getMaxGold(int peopleCount,int poolNum) {
22         int maxGold=0;
23         //m个人挖n个矿时金币数的备忘,遇到相同数量时直接得到结果
24         if(backup[peopleCount][poolNum]!=-1) {
25             maxGold=backup[peopleCount][poolNum];
26         } else if(poolNum==0) {
27             // 只剩下一个矿，人数够，金币数为矿值,人数不够为0
28             if(peopleCount>=peopleNeed[poolNum]) {
29                 maxGold=goldEach[poolNum];
30             } else {
31                 maxGold=0;
32             }
33         } else if(peopleCount>=peopleNeed[poolNum]) {
34             // 不是只剩下一个矿，且人数大于挖当前矿需要的人数，
35             // 挖当前矿时，获得的最大金币为 剩下的人数减去挖当前矿需要的人数 去挖 除去当前矿剩下的矿获得的金币值 加上当前矿能挖出的金币值
36             // 不挖当前矿时，获得的最大金币为 当前剩下的所有人 去挖 除去当前矿剩下的矿获得的金币值
37             // 两者中的最大值为 剩余人数挖剩余矿时获得金币的最大值
38             maxGold=Math.max(getMaxGold(peopleCount-peopleNeed[poolNum],poolNum-1)+goldEach[poolNum],
39                     getMaxGold(peopleCount,poolNum-1));
40         } else {
41             // 不是只剩下一个矿，剩余人数小于挖当前矿需要的人数，
42             // 当前剩下的所有人数去挖除去当前矿剩下的矿所得的金币数
43             maxGold=getMaxGold(peopleCount,poolNum-1);
44         }
45         // 将当前人数挖当前矿数获得金币的最大值保存
46         backup[peopleCount][poolNum]=maxGold;
47         return maxGold;
48     }
49 }