C++에서 숫자 높거나 낮은 II 추측하기

<시간/>

추측 게임을 한다고 가정합니다. 게임의 규칙은 다음과 같습니다 -

Player1은 1에서 n까지의 숫자를 선택합니다. player2는 player1이 선택한 숫자를 추측해야 합니다.
player2가 잘못 추측할 때마다 player1은 선택한 숫자가 더 높거나 낮은지 알려줍니다.

그러나 플레이어가 특정 숫자 x를 추측하고 다른 플레이어가 잘못 추측하면 다른 플레이어는 $x를 지불해야 합니다. player2가 정답을 맞추면 게임이 종료됩니다.

예를 들어 n =10이고 player1이 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
낮은 범위에서 높은 범위에 있는 i의 경우
- ans :=ans의 최소값 및 (i + 비용의 최대값(low, i – 1, dp) 및 비용(i + 1, high, dp))
dp[low, high] :=ans 및 return as
실제 방법은 다음과 같습니다 -
(n + 1) x (n + 1) 크기의 dp라는 2차원 배열을 하나 만들고 -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;
}

C++에서 숫자 높거나 낮은 II 추측하기

예시

입력

출력