C++での数値の上位または下位IIを推測します

推測ゲームをプレイしているとします。ゲームのルールは次のとおりです-

• Player1は、1からnまでの数字を選択します。 player2は、player1が選択した番号を推測する必要があります。
• player2が間違って推測するたびに、player1は選択された数字が多いか少ないかを判断します。

ただし、あるプレーヤーが特定の数字xを推測し、別のプレーヤーが間違って推測した場合、別のプレーヤーは$xを支払う必要があります。 player2が正解すると、ゲームは終了します。

たとえば、n =10で、player1が8を取っている場合

• 最初のラウンドで、player2は数字が5であると言います。これは間違っています。実際の数字はもっと高いので、$5を与えます
• 第2ラウンドで、player2は数字が7であると言います。これは間違っています。実際の数字はもっと高いので、$7を与えます
• 第3ラウンドで、player2は数字が9であると言います。これは間違っています。実際の数字はもっと低く、$9を与えます

これでゲームは終了します。したがって、与えられる合計金額は$ 5 + $ 7 + $ 9 =$21です。

これを解決するには、次の手順に従います-

• コストと呼ばれる1つのメソッドを作成します。これは、低、高、別のテーブルdpを使用します
• 低>=高の場合、0を返します
• dp [low、high]が-1でない場合は、dp [low、high]を返します
• ans：=inf
• 低から高の範囲のiの場合
  • ans：=ansの最小値と（i +コストの最大値（low、i – 1、dp）およびcost（i + 1、high、dp））
• dp [low、high]：=ansおよびreturnans
• 実際の方法は次のようになります-
• サイズ（n + 1）x（n + 1）のdpと呼ばれる1つの2D配列を作成し、これに-1を入力します
• 返品コスト（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