记忆化搜索系列一＞猜数字大小II

class Solution {
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n+1][n+1];
        return dfs(1,n);
    }

    private int dfs(int left, int rigth){
        
        if(left >= rigth) return 0;//递归出口，不存在(>)和不用花钱)(=)
        
        if(memo[left][rigth] != 0) return memo[left][rigth];

        int ret = 0x3f3f3f3f;
        for(int head = left; head <= rigth; head++){
            int x = dfs(left,head-1);//猜大了
            int y = dfs(head+1,rigth);//猜小了
            ret = Math.min(Math.max(x,y)+head, ret);
        }

        memo[left][rigth] = ret;
        return memo[left][rigth];
    }
}