// https://discuss.leetcode.com/topic/51353/simple-dp-solution-with-explanation

// https://en.wikipedia.org/wiki/Minimax

// 开始我的思路有问题，我是先选择区间，最后收敛到结果数

// 实际上work的思路是，先选择数字，再走向某个区间，然后取两个区间中的更大值

class Solution {

    int ** table;

    int DP(int s, int e) {

        if (s >= e) {

            return 0;

        }

        if (table[s][e] != INT_MAX) {

            return table[s][e];

        }

        int local_max = INT_MAX;

        for (int k=s; k<=e; ++k) {

            // 下面这个表达式很重要

            local_max = min(k + max(DP(s, k-1), DP(k+1, e)), local_max);

        }

        table[s][e] = local_max;

        return local_max;

    }

public:

    int getMoneyAmount(int n) {

        table = new int*[n+1];

        for (int i=0; i<n+1; ++i) {

            table[i] = new int[n+1];

            for (int j=0; j<n+1; ++j) {

                table[i][j] = INT_MAX;

            }

        }

        int ret = DP(1, n);

        for (int i=0; i<n+1; ++i) {

            delete[] table[i];

        }

        delete[] table;

        return ret;

    }

};

// 用Java又做了一遍

package com.company;

import java.util.ArrayList;

import java.util.List;

class Solution {

    int[][] dp;

    int get(int s, int e) {

        if (s >= e) {

            // 注意,只有一个的话,不用猜

            return 0;

        }

        if (dp[s][e] != 0) {

            return dp[s][e];

        }

        // 注意Java的是这种形式的MIN/MAX

        int min = Integer.MAX_VALUE;

        for (int i=s; i<=e; i++) {

            int tmp = Math.max(get(s, i-1), get(i+1, e)) + i;

            if (tmp < min) {

                min = tmp;

            }

        }

        dp[s][e] = min;

        return min;

    }

    public int getMoneyAmount(int n) {

        // 看了之前做的内容,思路还是很清晰的

        // 要用DP的时候,不要犹豫

        dp =new int[n+1][n+1];

        int ret = get(1, n);

        return ret;

    }

}

public class Main {

    public static void main(String[] args) {

        // write your code here

        System.out.println("Hello");

        Solution solution = new Solution();

        int ret = solution.getMoneyAmount(3);

        System.out.printf("Get ret: %d\n", ret);

    }

}