class Solution {
    public int getMoneyAmount(int n) {
        int[][] money = new int[n][n];
        for (int[] m: money) {
            Arrays.fill(m, Integer.MAX_VALUE);
        }
        for (int i=0; i<n; i++) {
            money[i][i] = 0;
            if (i + 1 < n) {
                money[i][i+1] = i + 1;
            }
        }

        for (int len=3; len<=n; len++) {
            for (int i=0; i<=n-len; i++) {
                for (int j=i; j<i+len; j++) {
                    if (i == j) {
                        money[i][i+len-1] = Math.min(money[i][i+len-1], 
                            (j+1) + money[j+1][i+len-1]);
                    }else if (j == i + len - 1) {
                        money[i][i+len-1] = Math.min(money[i][i+len-1], 
                            money[i][j-1] + (j+1));
                    }else{
                        money[i][i+len-1] = Math.min(money[i][i+len-1], 
                        (j+1) + Math.max(money[i][j-1], money[j+1][i+len-1]));
                    }
                }
            }
        }

        return money[0][n-1];
    }
}