leetcode 375 猜数字游戏2

63 阅读 0 评论 42 点赞

我是靠谱客的博主顺心悟空，最近开发中收集的这篇文章主要介绍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）。这里的最少钱指的是

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

所有的数字。

代码：

 1 class Solution {
 2
public int getMoneyAmount(int n) {
 3
int[][] opt = new int[n + 1][n + 1];
 4
 5
for (int i = 1; i <= n; i++) {
 6
opt[i][i] = 0;
 7 
}
 8
 9
for (int i = n; i >= 1; i--) {
10
for (int j = i + 1; j <= n; j++) {
11
opt[i][j] = Integer.MAX_VALUE;
12
for (int k = i; k <= j; k++) {
13
int left = k == i ? 0 : opt[i][k - 1];
14
int right = k == j ? 0 : opt[k + 1][j];
15
opt[i][j] = Math.min(opt[i][j], k + Math.max(left, right));
16 
}
17 
}
18 
}
19
20
return opt[1][n];
21 
}
22 }