leetcode 375. Guess Number Higher or Lower II | 375. 猜数字大小 II（动态规划思路总结）

超、凢脫俗 2022-08-31 01:58 61阅读 0赞

## 题目 ##

[https://leetcode.com/problems/guess-number-higher-or-lower-ii/][https_leetcode.com_problems_guess-number-higher-or-lower-ii]  
![在这里插入图片描述][a9f51c25642089fcf9065a19ec7517f5.png]

## 题解 ##

首先，看了 Related Topics，知道这是个 dp 问题。  
![在这里插入图片描述][15a98acb6c6f6f30823d13a58b533248.png]

##### 动态规划思路总结 #####

根据 dp 的常规流程，先选几个 **计算量较小** 的输入，手动尝试一下，**找感觉**。

然后 **逐渐扩大** 输入的数，发现 **计算量剧增**，手动计算已经很难列出所有情况了。出现这种现象大多数是因为，你的尝试的过程，实际上是 **将递归暴力展开** 的过程。

展开的项数多了之后，你会隐隐约约的感觉到：**有些部分被重复计算了**！

然后，你要 **让这种模糊的感觉变得清晰**（我称之为玄学…）。因为这就是使用 dp 的目的：存储已经计算过的状态，避免重复计算。

让模糊的感觉变清晰的过程，就是把 **递归变成 dp** 的过程，具体方法可以是：写出递归需要的参数，分别将这些参数作为 dp 数组的维度，dp 存储值的就是题目要求解的值。

这样你就 **设计出了 dp 数组**。先把 dp 数组的 **默认值、初始值** 填好，再看看 **还有那些容易计算的数**，**依次计算** 它们（不一定是从左到右。还可能是上下相关，可能是斜向，也可能是像累加和那样的索引下标访问）。你在这个过程中填充 dp 数组的顺序，就是用代码实现时填充 dp 数组的顺序。

填完 dp 数组之后，答案就呼之欲出了。剩下的就是对 dp 数组的空间优化，这里不再详述。

附上做这题的草稿，大概就是上述的尝试过程。  
![在这里插入图片描述][63ff80c5c983affa857ff5ad1de4f441.png]

class Solution { 
        public int getMoneyAmount(int n) { 
            int[][] dp = new int[n + 2][n + 2]; // 二维表示左右边界, 用n+2作为冗余0可省略越界判断
            for (int i = 2; i <= n; i++) {  // dp[L][R] 当L=R时值为0，可以直接从i=2开始
                for (int j = i; j <= n; j++) {   
                    int L = j - i + 1;
                    int R = j;
                    int min = Integer.MAX_VALUE;
                    for (int M = L; M <= R; M++) {  // M从L到R，找到所有M情况下的min
                        // [L...M-1] + M + [M+1...R]
                        min = Math.min(min, Math.max(dp[L][M - 1], dp[M + 1][R]) + M);
                    }
                    dp[L][R] = min;
                }
            }
            return dp[1][n];
        }
    }

![在这里插入图片描述][f1d405e1c85dc12c873fad0e73a474f8.png]

[https_leetcode.com_problems_guess-number-higher-or-lower-ii]: https://leetcode.com/problems/guess-number-higher-or-lower-ii/
[a9f51c25642089fcf9065a19ec7517f5.png]: /images/20220829/6a6acf15bc5a4e95bb8c77fe94aefcd3.png
[15a98acb6c6f6f30823d13a58b533248.png]: /images/20220829/edd3479fa9594b609c8802e0cbcdbe26.png
[63ff80c5c983affa857ff5ad1de4f441.png]: /images/20220829/ddee82ba61014052a4600c0ce1d454cf.png
[f1d405e1c85dc12c873fad0e73a474f8.png]: /images/20220829/bb5cb9b220bb4f56948b91cb7795e8e3.png