375. Guess Number Higher or Lower II - cocoder39/coco39_LC GitHub Wiki
375. Guess Number Higher or Lower II
minimize the worst cost. f(i, j) = min{k + max{f(i, k - 1), f(k + 1, j)}}. what we can do at current step is min the cost among all out choices i <= k <= j. what about next step? well, we cannot do anything for next step at current step, thus we have to consider the worst case.
eg. given range [1, 2]. we can choose either 1 or 2. if we choose 1 and found it was incorrect (worst case), we will pay 1 buck and choose 2. if we choose 2 and found it was incorrect (worst case), we will pay 2 bucks then choose 1 to win. With regard to considering those worst cases, we would choose 1.
the dp state transition is alike 312. Burst Balloons. corner cases:
- dp[i][i]
- dp[left][choice - 1] when choice == left
- dp[choice + 1][right] when choice == right
int getMoneyAmount(int n) {
//dp[i][j] is cost to guarantee a win within range [i .. j]
vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX));
for (int i = 1; i <= n; i++) { //len == 1
dp[i][i] = 0; //guarantee win without cost
}
for (int len = 2; len <= n; len++) {
for (int left = 1; left - 1 + len <= n; left++) {
int right = left - 1 + len;
for (int choice = left; choice <= right; choice++) {
dp[left][right] = min(dp[left][right],
choice + max(choice == left ? 0 : dp[left][choice - 1],
choice == right ? 0 :dp[choice + 1][right]));
}
}
}
return dp[1][n];
}
follow up: minimize expected loss instead of worst loss.