375. Guess Number Higher or Lower II

// https://leetcode.com/problems/guess-number-higher-or-lower-ii/discuss/84764/Simple-DP-solution-with-explanation~~
// Time: O(n3), Space: O(n2)
// See solution for explaintaion on the k=(i+j)/2 setiing
// Also, see submission most fast solution for best recrusive solution
class Solution {
    public int getMoneyAmount(int n) {
        if (n <= 1) {
            return 0;
        }

        int[][] dp = new int[n+1][n+1];
        for (int l=2; l<=n; l++) {
            for (int i=1; i+l-1<=n; i++) {
                int j = i+l-1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k=(i+j)/2; k<=j; k++) {
                    int tmp = k + Math.max(k-1 >= i ? dp[i][k-1] : 0, k+1 <= j ? dp[k+1][j] : 0);
                    dp[i][j] = Math.min(dp[i][j], tmp);
                }
            }
        }

        return dp[1][n];
    }
}