leetcode 375 猜数字游戏2

题意：

在1的基础上，猜错一次罚款对应的钱数，问最少需要多少钱保证一定能猜对。

 

思路：

直觉告诉我们可以用dp。但这题难在如何理解需要dp的变量以及dp的方程式怎么写。

dp的作用是遍历所有可能的情况并选出最优的情况。考虑的关键是如何把原问题分解成子问题。

注意到在原问题里，我们是在1~n的区间里猜数。每猜一次数，这个区间就会缩小。如第一次猜的

是x，则新的区间无非是1~x-1或x+1~n。也就是说这里需要dp的变量可以用一个矩阵表示，即

dp[lower_bound][upper_bound]。这里我们需要考虑在所有最坏情况分支中的最好情况（最小钱数）。

即将dp[i][j]这个区间内猜数，dp[i][j] = min{max{dp[i][k-1], dp[k+1][j]} + k}。

 

至于初始化，是典型的对角初始化，即i=j时，dp[i][j]=0（即一次猜中，不存在猜错的罚款）。

最后求出结果dp[1][n]即我们想要的结果。

 

总结来说，这题和一个典型的dp问题——从楼上扔鸡蛋问题很像。除了构造出方程式外，重点

还在于怎么理解最少需要多少钱这个概念，即极大值最小化问题（minmax）。这里的最少钱指的是

在所有可能的最坏情况下所能得到的最优方案。根据这个方案我们可以用不超出结果罚款的钱数猜出

所有的数字。

 

代码：

class Solution {
    public int getMoneyAmount(int n) {
        int[][] opt = new int[n + 1][n + 1];
        
        for (int i = 1; i <= n; i++) {
            opt[i][i] = 0;
        }
        
        for (int i = n; i >= 1; i--) {
            for (int j = i + 1; j <= n; j++) {
                opt[i][j] = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    int left = k == i ? 0 : opt[i][k - 1];
                    int right = k == j ? 0 : opt[k + 1][j];
                    opt[i][j] = Math.min(opt[i][j], k + Math.max(left, right));
                }
            }
        }
        
        return opt[1][n];
    }
}