We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5. Second round: You guess 7, I tell you that it's higher. You pay $7. Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
----------------------/* The guess API is defined in the parent class GuessGame. @param num, your guess @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); */ public class Solution extends GuessGame { public int guessNumber(int n) { int left = 1, right = n; while (left <= right) { int mid = (right - left) / 2 + left; int rt = guess(mid); if (rt == 0) return mid; if (rt > 0) { left = mid + 1; }else { right = mid - 1; } } return left; } }
375. Guess Number Higher or Lower II
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5. Second round: You guess 7, I tell you that it's higher. You pay $7. Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
-----------------------------题意有点绕:找一个花费最小的通解
brute force的算法是枚举所有的可能性,找出最小(最优)的解。
给定[start, end], 猜i点之后的cost是cost[i] = i + Math.max(cost[start, i - end], cost[i + 1, end]), 取2者中间最大是因为不能确定最终结果在左还是在右
ref: https://leetcode.com/problems/guess-number-higher-or-lower-ii/solution/
Solution #1 DP 是对brute force的优化
重点:这题的2维DP是按对角线来填充,因为[len]是基于[len - i]...[len - 1]
以后写dp要理解其本身的通项公式
O(n^3)
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 + 2; start++) { int min = Integer.MAX_VALUE; for (int i = start; i <= start + len - 1; i++) { int v = 0; if (i == start + len - 1) { v = i + dp[start][i - 1]; }else v = i + Math.max(dp[start][i - 1], dp[i + 1][start + len - 1]); min = Math.min(min, v); } dp[start][start + len - 1] = min; } } return dp[1][n]; } }进一步优化: [start, (start + end) / 2] 永远比 [(start + end) / 2, end]小,所以只需计算后半部分。BigO不变
No comments:
Post a Comment