Monday, November 13, 2017

[LeetCode]Guess Number Higher or Lower II

题目的描述很不清楚,我们需要弄清楚它的意思。它的意思是,对于1-n的数,主持人选择任意的数k,求我们需要的最少的钱来赢的这个游戏。例如:1,2,3,我们有以下情况:

  • 如果我们先取1,最坏的情况cost = 3
    • 假设k = 1,cost = 0
    • 假设k = 3,我们取1之后只需要最多花两块钱就可以赢,因为我们直接取2,如果不是答案我们立马就可以知道答案是3。假设我们取3的话我们需要花费更多的钱,cost = 3
    • 同理k = 2,cost = 1,因为我们之后一定取2,应为cost更少
  • 如果我们先取2,最坏情况cost = 3
    • 假设k = 2, cost = 0
    • 假设k = 1, cost = 2
    • 假设k = 3,cost = 2 + 1 = 3
  • 如果先取3,最坏情况cost = 4
    • 假设k = 3, cost = 0
    • 假设k = 1,cost = 3
    • 假设k = 2,cost = 3 + 1 = 4
所以最小的cost的情况对于我们先取1或者2的情况,我们需要3块钱来保证赢。我们假设用cost[i][j]来表示对于[i, j]范围我们保证可以赢的最小资金。递推公式为:
  • cost[i][j] = min(k + max(cost[i][k - 1], cost[k + 1][j])), where i <= k <= j
max对应的是主持人选择的数在左半边或者右半边的更坏的情况,也就是使cost更贵的情况,如果选择的数就是k的话其cost显然更小,我们这里就不需要考虑了。我们要取更坏的情况。min对应的是这次pick我们取的数能使总的cost[i][j]更小的情况,显然对于[i,j]的数,我们应该选择能使cost[i][j]最小的数来进行游戏。假设输入1-n的数,时间复杂度O(n^3),空间复杂度O(n^2),代码如下:


No comments:

Post a Comment