1 public class test 2 { 3     public static void main(String[] args) 4     { 5         Scanner input = new Scanner(System.in); 6         int n = input.nextInt(); 7         //第一个位置不使用 8         int[] prices = new int[] {0,1,5,8,9,10,17,17,20,24,30}; 9         int[] r = new int[n + 1];10         for(int i = 0; i < r.length; i++)11             r[i] = Integer.MIN_VALUE;12         System.out.println(MaxProfit(n, prices, r));13     }    14     15     //recursion16     public static int MaxProfit(int n, int[] prices, int[] r)17     {18         if(n == 0)19             return 0;20         21         int tmpMax = Integer.MIN_VALUE;22         for(int i = 1; i <= n; i++)23         {24             //避免重复计算25             if(r[n - i] == Integer.MIN_VALUE)26                 r[n - i] = MaxProfit(n - i, prices, r);27             tmpMax = Math.max(tmpMax, prices[i] + r[n - i]);28         }29         30         return tmpMax;31     }32     33     //iteration 时间复杂度: O(N^2)34     public static int MaxProfit(int n, int[] prices, int[] r)35     {36         r[0] = 0;37         for(int i = 1; i <= n; i++)38             for(int j = 1; j <= i; j++)39                 r[i] = Math.max(r[i], prices[j] + r[i - j]);40         41         return r[n];42     }43 }