Đoán số cao hơn hoặc thấp hơn II trong C ++

Giả sử chúng ta đang chơi Trò chơi Đoán. Luật chơi như sau -

Người chơi 1 chọn một số từ 1 đến n. người chơi 2 phải đoán số nào được chọn bởi người chơi 1.
Mỗi khi người chơi 2 đoán sai, người chơi 1 sẽ cho biết số được chọn cao hơn hay thấp hơn.

Tuy nhiên, khi một người chơi đoán một số cụ thể x và một người chơi khác đoán sai, người chơi khác phải trả $ x. Trò chơi sẽ kết thúc khi người chơi 2 có câu trả lời chính xác.

Ví dụ:nếu n =10 và người chơi 1 đã lấy 8

Ở vòng đầu tiên, người chơi 2 nói với số là 5, điều đó là sai, số thực tế cao hơn, thì anh ta sẽ đưa ra 5 đô la
Trong vòng thứ hai, người chơi 2 nói với số là 7, điều đó là sai, số thực tế cao hơn, thì anh ta sẽ đưa ra 7 đô la
Trong vòng thứ ba, người chơi 2 nói với số là 9, điều đó là sai, số thực tế thấp hơn, sau đó anh ta sẽ đưa ra 9 đô la

Bây giờ trò chơi kết thúc. Vì vậy, tổng số tiền đã cho là 5 đô la + 7 đô la + 9 đô la =21 đô la.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

tạo một phương pháp được gọi là chi phí, lấy giá trị thấp, cao, một bảng dp khác
nếu thấp> =cao, trả về 0
nếu dp [low, high] không phải là -1, thì trả về dp [low, high]
ans:=inf
cho tôi trong phạm vi từ thấp đến cao
- ans:=min of ans và (i + max của chi phí (thấp, i - 1, dp) và chi phí (i + 1, cao, dp))
dp [low, high]:=ans và trả về ans
Phương pháp thực tế sẽ như thế nào -
tạo một mảng 2d được gọi là dp có kích thước (n + 1) x (n + 1) và điền vào mảng này với -1
chi phí trả lại (1, n, dp)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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;
}

Đoán số cao hơn hoặc thấp hơn II trong C ++

Ví dụ

Đầu vào

Đầu ra