375. 猜数字大小 II

class Solution {
    Long [][] memo;
    /**
    记忆化递归
     */
    public int getMoneyAmount(int n) {
        memo=new Long[n+1][n+1];
        return (int)helper(1,n);

    }
    public long helper(int low,int high){
        if(low>=high){//猜对了 或者越界
            return 0;
        }
        if(memo[low][high]!=null){
            return memo[low][high];
        }
        long min=Integer.MAX_VALUE;
        long res=0;
        for(int i=low;i<=high;i++){
            res=( i+Math.max(helper(low,i-1),helper(i+1,high)) );//一定要最大值,满足两者才可以          
            min=Math.min(min,res);
        }
         memo[low][high]=min;
        return min;
    }
}