1 public class Solution { 2     public int getMoneyAmount(int n) { 3         int[][] dp = new int[n + 2][n + 2]; 4         for (int len = 1; len < n; len++) { 5             for (int left = 1; left <= n - len; left++) { 6                 int right = left + len; 7                 dp[left][right] = Integer.MAX_VALUE; 8                 for (int k = left; k <= right; k++) { 9                     dp[left][right] = Math.min(dp[left][right], k + Math.max(dp[left][k-1], dp[k+1][right]));10                 }11             }12         }13         return dp[1][n];14     }15 }