C++ dp solution and its follow up

• 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];
}
};

``````

• 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)``

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