資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 實現猜數字大小 II
假設我們正在玩猜數字遊戲。遊戲規則如下：
- 玩家1 從 1 到 n 中選擇一個數字。玩家2 必須猜出玩家1 選擇的數字。
- 每次玩家2 猜錯，玩家1 會告訴他選擇的數字是更大還是更小。
但是，當一個玩家猜出一個特定數字 x，而另一個玩家猜錯時，另一個玩家必須支付 $x。當玩家2 猜對時，遊戲結束。
例如，如果 n = 10，玩家1 選擇了 8
- 第一輪，玩家2 猜數字是 5，猜錯了，實際數字更大，那麼他需要支付 $5
- 第二輪，玩家2 猜數字是 7，猜錯了，實際數字更大，那麼他需要支付 $7
- 第三輪，玩家2 猜數字是 9，猜錯了，實際數字更小，那麼他需要支付 $9
現在遊戲結束。所以總共支付的金額是 $5 + $7 + $9 = $21。
為了解決這個問題，我們將遵循以下步驟：
- 建立一個名為 cost 的方法，它接收 low、high 和另一個表 dp 作為引數
- 如果 low >= high，則返回 0
- 如果 dp[low, high] 不為 -1，則返回 dp[low, high]
- ans := inf
- 對於 i 從 low 到 high 的範圍
- ans := ans 和 (i + cost(low, i – 1, dp) 和 cost(i + 1, high, dp) 的最大值) 的最小值
- dp[low, high] := ans 並返回 ans
- 實際方法如下：
- 建立一個名為 dp 的二維陣列，大小為 (n + 1) x (n + 1)，並將其全部填充為 -1
- 返回 cost(1, n, dp)
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int cost(int low, int high, vector < vector <int> >& dp){
if(low >= high)return 0;
if(dp[low][high] != -1)return dp[low][high];
int ans = INT_MAX;
for(int i = low; i <= high; i++){
ans = min(ans, i + max(cost(low, i - 1, dp), cost(i + 1, high, dp)));
}
return dp[low][high] = ans;
}
int getMoneyAmount(int n) {
vector < vector <int> > dp(n + 1, vector <int> (n + 1, -1));
return cost(1, n, dp);
}
};
int main() {
Solution ob1;
cout << ob1.getMoneyAmount(8) << endl;
return 0;
}輸入
8
輸出
12
更新於: 2020年4月29日
260 次檢視
廣告