Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2214.html
2214. Minimum Health to Beat Game (Medium)
You are playing a game that has n
levels numbered from 0
to n  1
. You are given a 0indexed integer array damage
where damage[i]
is the amount of health you will lose to complete the i^{th}
level.
You are also given an integer armor
. You may use your armor ability at most once during the game on any level which will protect you from at most armor
damage.
You must complete the levels in order and your health must be greater than 0
at all times to beat the game.
Return the minimum health you need to start with to beat the game.
Example 1:
Input: damage = [2,7,4,3], armor = 4 Output: 13 Explanation: One optimal way to beat the game starting at 13 health is: On round 1, take 2 damage. You have 13  2 = 11 health. On round 2, take 7 damage. You have 11  7 = 4 health. On round 3, use your armor to protect you from 4 damage. You have 4  0 = 4 health. On round 4, take 3 damage. You have 4  3 = 1 health. Note that 13 is the minimum health you need to start with to beat the game.
Example 2:
Input: damage = [2,5,3,4], armor = 7 Output: 10 Explanation: One optimal way to beat the game starting at 10 health is: On round 1, take 2 damage. You have 10  2 = 8 health. On round 2, use your armor to protect you from 5 damage. You have 8  0 = 8 health. On round 3, take 3 damage. You have 8  3 = 5 health. On round 4, take 4 damage. You have 5  4 = 1 health. Note that 10 is the minimum health you need to start with to beat the game.
Example 3:
Input: damage = [3,3,3], armor = 0 Output: 10 Explanation: One optimal way to beat the game starting at 10 health is: On round 1, take 3 damage. You have 10  3 = 7 health. On round 2, take 3 damage. You have 7  3 = 4 health. On round 3, take 3 damage. You have 4  3 = 1 health. Note that you did not use your armor ability.
Constraints:
n == damage.length
1 <= n <= 10^{5}
0 <= damage[i] <= 10^{5}
0 <= armor <= 10^{5}
Related Topics:
Array, Greedy, Prefix Sum
Similar Questions:
Solution 1. DP
Let yes
be the min health needed if we do use armor once.
Let no
be the min health needed if we don’t use armor.
Both of them are initialized as 1
.
From A[N1]
to A[0]
, at each step, we get newYes
and newNo
values:
newNo
is simplyno + A[i]
.newYes
has two options. It’s the min of these two: Use the armor in the current level. The min health needed is
no + max(0, A[i]  armor)
.  Don’t use the armor in the current level but a previous level. The min health needed is
yes + A[i]
.
 Use the armor in the current level. The min health needed is
In the end, the result is min(yes, no)
.
// OJ: https://leetcode.com/problems/minimumhealthtobeatgame/
// Time: O()
// Space: O()
class Solution {
public:
long long minimumHealth(vector<int>& A, int armor) {
long yes = 1, no = 1;
for (int i = A.size()  1; i >= 0; i) {
long newYes = min(no + max(0, A[i]  armor), yes + A[i]);
long newNo = no + A[i];
yes = newYes, no = newNo;
}
return min(yes, no);
}
};
Solution 2. Greedy
We greedily use the armor at the level with the greatest damage. Without armor, we need 1 + sum(A)
min health. The armor can take damange of min(max(A), armor)
, saving us this amount of health. So in total, we just need 1 + sum(A)  min(max(A), armor)
.

class Solution { public long minimumHealth(int[] damage, int armor) { long s = 0; int mx = damage[0]; for (int v : damage) { s += v; mx = Math.max(mx, v); } return s  Math.min(mx, armor) + 1; } }

// OJ: https://leetcode.com/problems/minimumhealthtobeatgame/ // Time: O(N) // Space: O(1) class Solution { public: long long minimumHealth(vector<int>& A, int armor) { return 1 + accumulate(begin(A), end(A), 0L)  min(*max_element(begin(A), end(A)), armor); } };

class Solution: def minimumHealth(self, damage: List[int], armor: int) > int: return sum(damage)  min(max(damage), armor) + 1