375、猜数字大小II
我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。
每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
示例:
n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。
游戏结束。8 就是我选的数字。
你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
题解
1、暴力求解
$cost(1,n) = i+max(cost(1,i - 1),cost(i+1,n)) low <= i <= high$
- 代码
// java
class Solution {
public int getMoneyAmount(int n) {
return calculate(1,n);
}
private int calculate(int low, int high) {
// 递归结束条件
if (low >= high) {
return 0;
}
int minres = Integer.MAX_VALUE;
// 递归搜索
for (int i = low,i <= high;i++) {
int res = i + Math.max(calculate(low,i-1),calculate(i+1,high));
int minres = Math.min(res,minres);
}
return minres;
}
}
2、优化的暴力递归
$cost(1,n) = i+max(cost(1,i - 1),cost(i+1,n)) (low+high)/2 <= i <= high$
- 代码
// java
class Solution {
public int getMoneyAmount(int n) {
return calculate(1,n);
}
private int calculate(int low, int high) {
// 递归结束条件
if (low >= high) {
return 0;
}
int minres = Integer.MAX_VALUE;
// 递归搜索
for (int i = (low+high)/2,i <= high;i++) {
int res = i + Math.max(calculate(low,i-1),calculate(i+1,high));
int minres = Math.min(res,minres);
}
return minres;
}
}
3、动态规划
- 二维动归
- 自下向上
$cost(i,j) = pivot+max(cost(i,pivot - 1),cost(pivoty+1,len)) i <= pivot <= len,len = j-i+1$
$dp(i,j) = min_{pivots(i,j)}(pivot+max(dp(1,pivot - 1),dp(pivoty+1,len))) i <= pivot <= len,len = j-i+1$
- 代码
// java
class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n+1][n+1];
for (int len = 2;len <= n;len++) {
for (int start = 1;start <= n - len + 1;start++) {
int minres = Integer.MAX_VALUE;
for (int piv = start;piv < start+ len -1;piv++) {
int res = piv + Math.ma(dp[start][piv-1],dp[piv+1][start + len - 1]);
minres = Math.min(res,minres);
}
}
}
return dp[1][n];
}
}
4、优化的动态规划
- 二维动归
- 自下向上
$dp(i,j) = min_{pivots(i+(len-1)/2,j)}(pivot+max(dp(1,pivot - 1),dp(pivoty+1,len))) i+len/2 <= pivot <= i+len,len = j-i+1$
- 代码
// java
class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n+1][n+1];
for (int len = 2;len <= n;len++) {
for (int start = 1;start <= n - len + 1;start++) {
int minres = Integer.MAX_VALUE;
// 求最优的minres
for (int piv = start+(len-1)/2;piv < start+ len -1;piv++) {
int res = piv + Math.max(dp[start][piv-1],dp[piv+1][start+len-1]);
minres = Math.min(res,minres);
}
// 更新dp数组
dp[start][start+len -1] = minres;
}
}
return dp[1][n];
}
}
5、1~2ms 记忆化递归
class Solution {
public int getMoneyAmount(int n) {
if(n == 1) return 0;
int[][] memo = new int[n+1][n+1];
return calculateMoney(1,n,memo);
}
private int calculateMoney(int low, int high, int[][] memo) {
if (low >= high) return 0;
if (memo[low][high] != 0) return memo[low][high];
int minRes = Integer.MAX_VALUE;
for (int i = (low+high)/2; i <= high; i++) {
int res = i + Math.max(calculateMoney(i + 1, high, memo), calculateMoney(low, i - 1, memo));
minRes = Math.min(res, minRes);
}
memo[low][high] = minRes;
return minRes;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
