Google面经题 guess game cost

google 一道面经题
第二道题目是guess number game with cost，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

。
有大神遇到过吗？这个题具体是什么呢？

1. f[i][i] = 0 for 1 <= i <= 100,
   
2. f[i][j] = min{max(f[i][k - 1], f[k + 1][j]) + k} for i < k < j,

复制代码

Guessing game - I pick a number between 1 and 100 and you   are trying to guess it. Every time you query a number I tell you if it is higher or lower. Part 1- Write the code of it, if cost of querying a number is equal. Part 2- How about if cost of querying number x is x? How would you change the algorithm?

[quote][url=forum.php?mod=redirect

大神可以说下解法吗？

user123456 发表于 2016-3-28 01:59
Guessing game - I pick a number between 1 and 100 and you   are trying to guess it. Every time you q ...

第二题 加入了cost， 那么是希望改binary search， 让cost减小么。请问思路是什么

f[i][i] = 0 for 1 <= i <= 100,
f[i][j] = min(max(f[i][k - 1], f[k + 1][j]) + k) for i < k < j,
另外再开一个数组g记录下最优决策时候的k，然后二分的时候替换m = (l + r) / 2为m = g[l][r]

补充内容 (2016-3-28 02:54):
这就是算导上最优二叉搜索树的应用。

补充内容 (2016-3-28 02:57):
补充了之后
f[i][i] = 0 for 1 <= i <= 100,
f[i][j] = min(max(f[i][k - 1], f[k + 1][j]) + k) for i < k < j
被吞了。。

ctzsm 发表于 2016-3-28 02:59

写了下Java code，不确定是不是对了

1. public class GuessNumberGameWithCost {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int res = guessGameFollowUp();
   
5.                 System.out.println(res);
   
6.         }
   
7. 
   
8.        
   
9.         public static int guessGameFollowUp() {
   
10.                 int[][] f = new int[100 + 1][100 + 1];
    
11.                 for (int i = 1; i <= 100; i++) {
    
12.                         f[i][i] = i;
    
13.                 }
    
14.                 for (int len = 2; len <= 100; len++) {
    
15.                         for (int i = 1; i <= 100 - len + 1; i++) {
    
16.                                 int j = i + len - 1;
    
17.                                
    
18.                                 if (len == 2) {
    
19.                                         f[i][j] = Math.max(f[i][i], f[j][j]);
    
20.                                 } else {
    
21.                                         f[i][j] = Integer.MAX_VALUE;
    
22.                                         for (int k = i + 1; k < j; k++) {
    
23.                                                 f[i][j] = Math.min(f[i][j], Math.max(f[i][k - 1], f[k + 1][j]) + k);
    
24.                                         }
    
25.                                 }
    
26.                         }
    
27.                 }
    
28. 
    
29.                 return f[1][100];
    
30.         }
    
31. }
    

复制代码

这段程序答案出来的有问题, 我在eclipse上跑了一下死452

bobzhang2004 发表于 2016-3-28 23:37
写了下Java code，不确定是不是对了

楼主请问dp的状态代表什么？

wsrrzxl 发表于 2016-4-7 06:25
楼主请问dp的状态代表什么？

dp[i][i] 应该是最小的cost 在range（i， i）之间inclusive。 所以dp[i][i] = 0 因为不需要 guess。