We are playing the Guess Game. The game is as follows:<\/p>\n\n\n\n
I pick a number from 1<\/strong> to n<\/strong>. You have to guess which number I picked.<\/p>\n\n\n\n Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.<\/p>\n\n\n\n However, when you guess a particular number x, and you guess wrong, you pay $x<\/strong>. You win the game when you guess the number I picked.<\/p>\n\n\n\n Example:<\/strong><\/p>\n\n\n\n Given a particular n \u2265 1<\/strong>, find out how much money you need to have to guarantee a win<\/strong>.<\/p>\n\n\n\n Use dp[l][r] to denote the min money to win the game if the current guessing range is [l, r], to guarantee a win, we need to try all possible numbers in [l, r]. Let say we guess K, we need to pay K and the game might continue if we were wrong. cost will be K + max(dp(l, K-1), dp(K+1, r)), we need max to cover all possible cases. Among all Ks, we picked the cheapest one.<\/p>\n\n\n\n dp[l][r] = min(k + max(dp[l][k – 1], dp[k+1][r]), for l <= k <= r.<\/p>\n\n\n\n Time complexity: O(n^3) <\/p>\n","protected":false},"excerpt":{"rendered":" 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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,27,177,398],"class_list":["post-6465","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-game","tag-medium","tag-on3","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6465","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6465"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6465\/revisions"}],"predecessor-version":[{"id":6467,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6465\/revisions\/6467"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6465"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6465"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6465"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}n = 10, I pick 8.\n\nFirst round: You guess 5, I tell you that it's higher. You pay $5.\nSecond round: You guess 7, I tell you that it's higher. You pay $7.\nThird round: You guess 9, I tell you that it's lower. You pay $9.\n\nGame over. 8 is the number I picked.\n\nYou end up paying $5 + $7 + $9 = $21.\n<\/pre>\n\n\n\n
Solution: DP<\/strong><\/h2>\n\n\n\n
Space complexity: O(n^2)<\/p>\n\n\n\nC++<\/h2>\n
\n\/\/ Author: Huahua\nclass Solution {\npublic:\n int getMoneyAmount(int n) {\n constexpr int kInf = 1e9;\n vectorPython3<\/h2>\n
\n# Author: Huahua\nclass Solution:\n def getMoneyAmount(self, n: int) -> int:\n @lru_cache(maxsize=None)\n def dp(l, r): \n return min([k + max(dp(l, k - 1), dp(k + 1, r)) \n for k in range(l, r + 1)]) if l < r else 0\n return dp(1, n)\n<\/pre>\n<\/div><\/div>\n\n\n\n