Leetcode--Java--375. 猜数字大小 II

题目描述

一个猜数游戏，游戏规则如下： 从 1 到 n 之间选择一个数字。 你来猜我选了哪个数字。 如果你猜到正确的数字，就会 赢得游戏 。 如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。 每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。如果你花光了钱，就会 输掉游戏 。给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。

样例描述

思路

动态规划 区间dp

1. 先进行状态表示，由于不知道目标是什么，要求的是所有可能目标值情况下对应每种猜法的最小值。
2. 状态计算，就是枚举可能有哪些猜法，比如[i， j]中可以猜i~j，答案是所有这些猜法的最坏情况下的最小值。（我们是可以决定第一次猜什么的，所以这里并不是找让所有猜法都满足的最大值） 选完后有三种情况，如果猜小了或者猜大了要继续动态规划，由于不知道目标值是在哪个区间，所以为了保证最坏情况下，这里要取两者的max，再加上猜第k个位置的代价。
3. 最后最坏情况下的最小值，就是上述所有的最坏情况猜法下再取最小的。

代码

class Solution {
          
   
    public int getMoneyAmount(int n) {
          
   
       int f[][] = new int[n + 2][n + 2]; //1开始，又枚举涉及到k + 1，所以要初始n + 2
       if (n < 2) return 0;
       //区间dp枚举框架，外层枚举长度，内层枚举左端点，保证右端点不越界
       for (int len = 2; len <= n; len ++ ) {
          
   
           for (int i = 1; i + len - 1 <= n; i ++ ) {
          
   
               int j = i + len - 1;
               //最终是取min，所以先设初始值为无穷大
               f[i][j] = Integer.MAX_VALUE;
               //枚举[i, j]区间内的所有点
               for (int k = i; k <= j; k ++ ) {
          
   
                   //目标在左右区间的最坏情况要用max求，再加上k的代价
                 f[i][j] = Math.min(f[i][j], Math.max(f[i][k - 1], f[k + 1][j]) + k);
               }
           }
       }
       //求[1, n]区间内
       return f[1][n];
    }
}