Guess Number Higher or Lower II - Teeeeeebag/LeetCode GitHub Wiki

1. Memorized DP

public class Solution {
    private int getMoneyAmount(int start, int end){
        if (start >= end){
            return 0;
        }   
        if (dp[start][end]!=0){
            return dp[start][end];
        }
        int res = Integer.MAX_VALUE; 
        for (int i=start; i<=end; ++i){
            //Attention: choose min among those values
            res = Math.min(i + Math.max(getMoneyAmount(start, i-1), getMoneyAmount(i+1, end)), res);
        }   
        dp[start][end] = res;
        return res;
    }   
    private int[][] dp;
    public int getMoneyAmount(int n) {
        dp = new int[n+1][n+1];
        return getMoneyAmount(1, n); 
    }   
}