375. Guess Number Higher or Lower II

Link

Solution

根據選擇的數字 i，來計算結果並找出結果中的最小值

   public int getMoneyAmount(int n) {
        int[][] dp = new int[n+1][n+1];
        return getMoneyAmount(dp, 1, n);
    }
    
    public int getMoneyAmount(int[][] dp, int s, int e){
        if(s >= e) return 0;
        if(dp[s][e] != 0) return dp[s][e];
        
        int min = Integer.MAX_VALUE;
        for(int i = s; i <= e; i++){
            //根據選擇的數字 i，來計算結果並找出結果中的最小值
            min = Math.min(min, Math.max(getMoneyAmount(dp, s, i-1), getMoneyAmount(dp, i+1, e)) + i);
        }
        
        dp[s][e] = min;
        return dp[s][e];
    }