在C ++中猜测数字的高低II

假设我们正在玩猜猜游戏。游戏的规则如下-

• Player1选择一个从1到n的数字。玩家2必须猜测玩家1选择了哪个号码。

• 每当玩家2猜错时，玩家1都会告诉您所选择的数字是更高还是更低。

但是，当一个玩家猜出一个特定的数字x时，另一个玩家猜错了，另一个玩家必须支付$ x。当player2得到正确答案后，游戏将结束。

例如，如果n = 10，而玩家1拿了8

• 在第一轮中，player2告诉数字是5，那是错误的，实际数字更高，那么他会给$ 5

• 在第二轮中，player2告诉数字是7，那是错误的，实际数字更高，那么他会给$ 7

• 在第三轮中，player2告诉数字为9，那是错误的，实际数字较低，那么他会给$ 9

现在游戏结束。因此，给定的总金额为$ 5 + $ 7 + $ 9 = $ 21。

为了解决这个问题，我们将遵循以下步骤-

• 创建一个称为成本的方法，即低，高，另一种表dp

• 如果低> =高，则返回0

• 如果dp [low，high]不为-1，则返回dp [low，high]

• ans：= inf

• 对于我范围从低到高

• ans：= ans的最小值和（i +最大成本（low，i – 1，dp）和cost（i + 1，高，dp））

• dp [low，high]：= ans并返回ans

• 实际的方法将是-

• 制作一个称为dp的2d数组，其大小为（n + 1）x（n + 1），并用-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