40ms c++ code, and the original recursive solution.


  • 0
    H

    The 40ms solution is:

    int getMoneyAmount(int n) {
        // idea: an array a[n][n], where a[i][j] denotes the minimum cost to guess correctly for numbers [i, j]
        // array lenth 1 -> 0; lenth 2 -> select smaller one; lenth 3 -> select middle;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0x7fffffff));
        for (int i = 1; i <= n; i++)dp[i][i] = 0;
        for (int i = 1; i <= n - 1; i++)dp[i][i + 1] = i;
        for (int i = 1; i <= n - 2; i++)dp[i][i + 2] = i + 1;
    
        // from lenth 3, fill the array out;
        for (int nn = 3; nn <= n; nn++)
        for (int m = 1; m <= n - nn; m++){
            int mini = 0x7fffffff;
            for (int i = m + 2; i < m + nn; i++){
                int l = dp[m][i - 1];
                int r = dp[i + 1][m + nn];
                mini = min(mini, max(l, r) + i);
            }
            dp[m][m + nn] = mini;
        }
        return dp[1][n];
    }
    

    The recursive solution. Not surprisingly that the recursive will timeout, but it is a good start point.

    int getMoneyAmount_br(int m, int n){ // minimum cost for a correct guess [m, n]
        if (m == n)
            return 0;
        if (n - m < 3)
            return (m + n) / 2;
        
        int mini = 0x7fffffff;
        for (int i = m + 2; i < n; i++){
    
            int l = getMoneyAmount_br(m, i - 1);
            int r = getMoneyAmount_br(i + 1, n);
            mini = min(mini, max(l, r) + i);
        }
    
        return mini;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.