C++ dp solution and its follow up


  • 1
    Y

    Let maxCost[i][j] be the maximum cost of range[i, j], expCost[i][j] be the expected cost of range [i, j].

    • If the range length is 1 (i.e., j == i), then we should always guess correctly, i.e., maxCost[i][i] = 0, expCost[i][i] = 0;
    • If the range length is 2 (i.e., j == i + 1), we are guessing from two numbers {i, i + 1}, where we should always guess i. In the worst case, we lose i bucks, i.e., maxCost[i][i + 1] = i. With probability 0.5, we lose i bucks, i.e., expCost[i][i + 1] = 0.5 * i;
    • If the range length is 3 (i.e., j == i + 2), we are guessing from three numbers {i, i + 1, i + 2}, where we always guess i + 1. In the worst case, we lose i + 1 bucks, i.e., maxCost[i][i + 2] = i + 1. With probability 2/3, we lose i + 1 bucks, i.e., expCost[i][i + 2] = 2/3 * (i + 1).
    • For range length l > 3, it can be easily solved with dp.

    Solution that minimizes the maximum cost, i.e., the minimum amount of money that guarantees a win

    class Solution {
    public:
        int getMoneyAmount(int n) {
            if (n <= 1) return 0;
            
            vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));   // dp[i][j]: min money to win in range [i, j]
            for (int l = 1; l < n; l++) {
                for (int i = 1; i <= n - l; i++) {
                    if (l == 1) dp[i][i + l] = i;
                    else if (l == 2) dp[i][i + l] = i + 1;
                    else {
                        int minCost = min(i + dp[i + 1][i + l], i + l + dp[i][i + l - 1]);
                        for (int j = i + 1; j < i + l; j++) {
                            minCost = min(minCost, j + max(dp[i][j - 1], dp[j + 1][i + l]));
                        }
                        dp[i][i + l] = minCost;
                    }
                }
            }
            
            return dp[1][n];
        }
    };
    

    Solution that minimizes the expected cost, i.e., on average the minimum amount of money needed

    class Solution {
    public:
        int getMoneyAmount(int n) {
            if (n <= 1) return 0;
            
            vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));   // dp[i][j]: min money to win in range [i, j]
            for (int l = 1; l < n; l++) {
                for (int i = 1; i <= n - l; i++) {
                    if (l == 1) dp[i][i + l] = i / 2.0;
                    else if (l == 2) dp[i][i + l] = (i + 1) * 2 / 3.0;
                    else {
                        double minCost = min(i + dp[i + 1][i + l], i + l + dp[i][i + l - 1]) * l / (l + 1.0);
                        for (int j = i + 1; j < i + l; j++) {
                            minCost = min(minCost, l / (l + 1.0) * (j + max((double)(j - i) / l * dp[i][j - 1], (double)(i + l - j) / l * dp[j + 1][i + l])));
                        }
                        dp[i][i + l] = minCost;
                    }
                }
            }
            
            return dp[1][n];
        }
    };
    
    

  • 1
    B

    Can you give a explanation of how is the average amount calculated?
    What dose this expression stand for?

    i + l + dp[i][i + l - 1]) * l / (l + 1.0)

Log in to reply
 

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