Guess Number Higher or Lower II[Math,Dynamic Programming,Game Theory]

https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/

We are playing the Guessing Game. The game will work as follows:

1. I pick a number between 1 and n.
2. You guess a number.
3. If you guess the right number, you win the game.
4. If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
5. Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.

Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.

 

Example 1:

Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
    - If this is my number, your total is $0. Otherwise, you pay $7.
    - If my number is higher, the range is [8,10]. Guess 9.
        - If this is my number, your total is $7. Otherwise, you pay $9.
        - If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
        - If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
    - If my number is lower, the range is [1,6]. Guess 3.
        - If this is my number, your total is $7. Otherwise, you pay $3.
        - If my number is higher, the range is [4,6]. Guess 5.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
            - If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
            - If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
        - If my number is lower, the range is [1,2]. Guess 1.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
            - If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.

Example 2:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

Example 3:

Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
- Guess 1.
    - If this is my number, your total is $0. Otherwise, you pay $1.
    - If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.

 

Constraints:

• 1 <= n <= 200

별로 좋아하는 유형의 문제가 아니다.

 

Coding으로 게임을 왜 하는거야 ㅠㅠ

 

그놈의 Dynamic programming!!

 

어떻게 되든 남는 Guess Traget 숫자가 3개 이하면 3개의 경우 가운데 숫자, 2개의 경우 작은 숫자를 Pick하면 끝난다는 건 알겠다.

 

Hint를 보아하니, 단순 Recursive가 아니고 DP를 이용해야 한다던데,, 

 

1. Python

 

봐도 모르겄다 이건

 

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        # DP table initialization
        dp = [[0]*(n+1) for _ in range(n+1)]

        # fill in the DP
        for length in range(2,n+1):
            for i in range(1,n-length+2):
                j = i + length - 1
                dp[i][j] = float('inf')
                for k in range(i,j):
                    cost = k + max(dp[i][k-1],dp[k+1][j])
                    dp[i][j] = min(dp[i][j],cost)
        return dp[1][n]

 

우리가 이 문제에서 해야 할 일은 숫자 범위 [1, n]에서 최악의 경우에도 이기기 위해 필요한 최소 비용을 계산하는 것입니다. 이 비용을 구하기 위해 다이나믹 프로그래밍(DP)을 사용합니다. 다음은 fill the DP table 부분에 대한 상세한 설명입니다. 1. DP 테이블 정의 및 초기화 우리는 dp[i][j]를 숫자 범위 [i, j]에서 최악의 경우를 고려했을 때 필요한 최소 비용으로 정의합니다. 예를 들어, dp[1][10]은 숫자 범위 [1, 10]에서 승리하기 위해 필요한 최소 비용입니다. 길이가 1인 범위, 즉 i == j인 경우에는 선택할 수 있는 숫자가 하나밖에 없으므로 비용이 0입니다. 2. 구간 길이에 따라 DP 테이블 채우기 우리는 작은 범위부터 시작해서 점차 큰 범위로 확장하면서 테이블을 채워 나갑니다. 이는 작은 부분 문제의 결과를 사용해서 더 큰 부분 문제를 해결하는 다이나믹 프로그래밍의 핵심 아이디어입니다. 여기서 length는 현재 채우려는 구간의 길이입니다. length=2부터 시작해서 점차 n까지 증가시키며 채워 나갑니다. 이렇게 함으로써 짧은 구간의 최적 비용을 먼저 계산하여, 이를 더 긴 구간을 계산할 때 재사용할 수 있습니다. 3. 각 구간의 시작점과 끝점 설정 각 구간의 시작점 i와 끝점 j를 설정합니다. i는 현재 구간의 시작점입니다. j는 i부터 length-1만큼 떨어진 위치가 되며, 구간의 끝점을 나타냅니다. 예를 들어, length=2일 때 구간 [1, 2], [2, 3], ..., [n-1, n]이 처리됩니다. 4. dp[i][j]의 초기값 설정 우리는 [i, j] 구간의 비용의 최소값을 찾아야 하므로, dp[i][j]를 일단 큰 값(float('inf'))으로 초기화합니다. 이후 최소값을 찾으면서 계속 업데이트할 것입니다. 5. 각 숫자 k를 기준으로 비용 계산 이제 [i, j] 범위에서 각 숫자 k를 추측해 보면서, 최악의 경우 발생할 수 있는 비용을 계산합니다. k는 [i, j] 구간에서 선택할 수 있는 숫자입니다. cost = k + max(dp[i][k - 1], dp[k + 1][j])는 숫자 k를 선택했을 때 최악의 경우 발생할 수 있는 비용을 의미합니다. k는 우리가 이 선택에 지불해야 할 비용입니다. max(dp[i][k - 1], dp[k + 1][j])는 숫자를 맞히지 못했을 때, 숫자가 k보다 크거나 작을 경우 발생하는 최악의 비용을 의미합니다. 최악의 경우를 고려해야 하므로, dp[i][k - 1]과 dp[k + 1][j] 중 더 큰 값을 선택합니다. dp[i][j] = min(dp[i][j], cost)는 dp[i][j]를 [i, j] 구간에서 최악의 경우 발생할 수 있는 최소 비용으로 업데이트합니다. 6. 최종 결과 반환 모든 구간에 대해 계산이 완료되면, dp[1][n]에 전체 범위 [1, n]에서 최악의 경우 발생할 수 있는 최소 비용이 저장됩니다. 이를 반환하면 문제의 정답을 얻을 수 있습니다. 전체 코드 전체 코드는 아래와 같습니다: 이 코드가 작동하는 원리는 작은 구간부터 최적의 비용을 계산해 나가면서, 더 큰 구간에서 그 결과를 재사용하여 점점 더 큰 범위에 대한 최적 비용을 구하는 것입니다.

 

머리로는 이해가 가는데,

 

백지에서 다시 코드를 짜 보라고 하면 쉽지 않을 거 같다.

 

2. C++

봐도 모르겄다

 

class Solution {
public:
    int getMoneyAmount(int n) {
        // vector<int> dp(n+1,0);
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));

        for(int length = 2; length<=n; length++){
            for(int i=1;i<=n-length+1;i++){
                int j = i + length - 1;
                dp[i][j] = INT_MAX;
                
                for(int k=i;k<j;k++){
                    int cost = k + max(dp[i][k-1],dp[k+1][j]);
                    dp[i][j] = min(cost,dp[i][j]);
                }
            }
        }
        return dp[1][n];
    }
};