camiloni42
BAN USER- 2of 2 votes
AnswersYou are the main character in a game where you have to defeat a number of enemies in order. The player has a strength value and an initial amount of money. Each enemy also has a strength value, plus a price.
- camiloni42 in United States
When facing each enemy you can either:
1) Fight him (if your strength is enough). You keep your money.
2) Bribe him (if you have the necessary money). You subtract the enemy's price from your money, and it joins you and adds its strength to yours.
Given a starting strength and amount of money, calculate the optimal strategy and the amount of money you end with (-1 if impossible).
This can be easily solved recursively in O(2^n) basically trying out each option at every enemy. But is there a polynomial solution, maybe involving DP?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm
The enemies must be fought in the order they are given, you cannot choose it.
- camiloni42 November 20, 2016
@ divm01986 We need to optimized for maximum money (i.e. spend as little as possible).
- camiloni42 November 21, 2016