leetcode 375. Guess Number Higher or Lower II 猜数游戏+动态规划DP+最大最小化问题

约定不等于承诺〃 2022-06-07 02:47 73阅读 0赞

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round: You guess 5, I tell you that it’s higher. You pay 5.  
Second round: You guess 7, I tell you that it’s higher. You pay 7.  
Third round: You guess 9, I tell you that it’s lower. You pay 9.

Game over. 8 is the number I picked.

You end up paying 5 + 7 + 9 = 21.  
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

在1-n个数里面，我们任意猜一个数(设为i)，保证获胜所花的钱应该为 i + max(w(1 ,i-1), w(i+1 ,n))，这里w(x,y))表示猜范围在(x,y)的数保证能赢应花的钱，则我们依次遍历 1-n作为猜的数，求出其中的最小值即为答案，即最小的最大值问题

建议和这道题[leetcode 374. Guess Number Higher or Lower 猜数游戏][leetcode 374. Guess Number Higher or Lower]一起学习

代码如下：

/* 
     * 这个事第二次遇到这样的DP动态规划问题
     * 我们需要按照一定的顺序计算dp的值，由于计算dp[i][j]时我们需要计算dp[i][j-1],dp[i+1][j]，
     * 所以我们按照j-i递增的顺序计算，即l区间长度len由短到长的顺序计算。
     * */
    class Solution 
    {
        public int getMoneyAmount(int n) 
        {
            int [][]dp=new int[n+1][n+1];
            for(int len=1;len<n;len++)
            {
                for(int i=0;i+len<=n;i++)
                {
                    int j=i+len;
                    int one=Integer.MAX_VALUE;
                    for(int k=i;k<=j;k++)
                    {
                        int tmp=k+ Math.max(k-1>=i?dp[i][k - 1]:0,k+1<=j?dp[k + 1][j]:0);
                        one=Math.min(one, tmp);
                    }
                    dp[i][j]=one;
                }
            }
    
            return dp[1][n];
            //return cost(dp,1,n);
        }
    
        /*
         * ，在1-n个数里面，我们任意猜一个数(设为i)，保证获胜所花的钱应该为 i + max(w(1 ,i-1), w(i+1 ,n))，
         * 这里w(x,y))表示猜范围在(x,y)的数保证能赢应花的钱，则我们依次遍历 1-n作为猜的数，
         * 求出其中的最小值即为答案，即最小的最大值问题
         * */
        public int cost(int[][] dp, int beg, int end) 
        {
            if(beg>=end)
                return 0;
            else if(dp[beg][end]!=0)
                return dp[beg][end];
            else 
            {
                int one=Integer.MAX_VALUE;
                for(int i=beg;i<=end;i++)
                {
                    int tmp=i+Math.max(cost(dp, beg, i-1), cost(dp, i+1, end));
                    one=Math.min(one, tmp);
                }
                dp[beg][end]=one;
                return one;
            }
        }
    }

下面是C++的做法，很不错，就是按照length去做DP动态规划

DFS的做法很不错，和这一道题[leetcode 329. Longest Increasing Path in a Matrix 矩阵中寻找最长递增序列 + 一个典型的深度优先遍历DFS的做法][leetcode 329. Longest Increasing Path in a Matrix _ _ _DFS] 的做法很相似，建议一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int getMoneyAmount(int n)
        {
            vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
            return dfs(dp, 1, n);
        }
    
        int dfs(vector<vector<int>>& dp, int beg, int end)
        {
            if (beg >= end)
                return 0;
            else if (dp[beg][end] != 0)
                return dp[beg][end];
            else
            {
                int one = INT_MAX;
                for (int i = beg; i <= end; i++)
                {
                    int a = i - 1 >= beg ? dfs(dp,beg,i-1) : 0;
                    int b = i + 1 <= end ? dfs(dp,i+1,end) : 0;
                    int tmp = i + max(a, b);
                    one = min(one, tmp);
                }
                dp[beg][end] = one;
                return dp[beg][end];
            }
        }
    
        int getMoneyAmountByDP(int n) 
        {
            vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
            for (int len = 1; len <= n; len++)
            {
                for (int i = 0; i + len <= n; i++)
                {
                    int j = i + len, one = INT_MAX;
                    for (int k = i; k <= j; k++)
                    {
                        int a = k - 1 >= i ? dp[i][k - 1] : 0;
                        int b = k + 1 <= j ? dp[k + 1][j] : 0;
                        int tmp = k + max(a,b);
                        one = min(one, tmp);
                    }
                    dp[i][j] = one;
                }
            }
            return dp[1][n];
        }
    };

[leetcode 374. Guess Number Higher or Lower]: http://blog.csdn.net/jackzhang_123/article/details/78173506
[leetcode 329. Longest Increasing Path in a Matrix _ _ _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78150769