Nice problem that can help you understand 2 key skills below:
- How to choose between Greedy and DP
Is the local optimal the ONLY option? Can other choices(computation pathes) contribute to current optimal value choise?
Considering this problem: on level i, can we simply pick the one with min Power? not really - because there's another factor to involve: Bullet #, that means, the one with min Power may not give you enough Bullet and then contribute to an optimal in future levels - So Greedy won't work. Then DP is the natural choice.
- DP optimization
This is step 2. When you write down the inital DP equation, give it another observation. In the inner-est loop, what you are trying to find out, is some minimal from the previous level - so, here we use Greedy by Sorting!
I enjoyed this problem a lot, which is marked as HARD on HackerRank. I assume HARD means, >1 key tricks combined.