$2.[$The Teacher $3]$: In the game "Teacher $3",$ the protagonist, Geralt of Oblivia, battles demons. We are nearing the completion of the game, with only one boss fight remaining.

Before facing the final boss, Geralt must confront $\backslash ($ n $\backslash )$ waves of monsters. Before each wave, he can purchase health potions to prepare for the upcoming fight. Any potions not used in one wave can be saved for subsequent waves. Monsters drop coins, which Geralt can use to buy more potions.

After researching online, we have gathered information about what to expect during each fight. In wave $\backslash ($ i $\backslash ),$ Geralt needs $\backslash ($ d$\_\{$i$\}\backslash )$ health potions to survive the wave. The cost of a potion before wave $\backslash ($ i $\backslash )$ is denoted by $\backslash ($ c$\_\{$i$\}\backslash ),$ and during wave $\backslash ($ i $\backslash ),$ the monsters will drop $\backslash ($ p$\_\{$i$\}\backslash )$ coins in total.

Our objective is to acquire enough potions before each wave to ensure Geralt's survival while minimizing the total amount of coins spent on the potions. The cost of potions before each wave depends on whether you play the game in the easy setting or the hard setting. Suppose that before the first wave, Geralt has no health potions, and he has $\backslash ($ P $\backslash )$ coins to purchase some. Note that if $\backslash ($ P $\backslash )$ is insufficient, it might be impossible for him to survive all the waves.

$($a$)[$Easy Mode$]$: In this scenario, the cost of a health potion decreases after each wave, i$.$e$.,\backslash ($ c$\_\{1\}>$c$\_\{2\}>\backslash$cdots$>$c$\_\{$n$\}\backslash ).$

i$.$

What is the best strategy to ensure Geralt's survival while optimizing the total remaining coin balance at the end of all waves? The complexity of your algorithm should be linear.

ii$.$ Argue that your algorithm is optimal.

$($b$)[$Hard Mode$]$: In this scenario, the cost of a health potion does not follow a particular pattern.

i$.$

To solve the problem, we have to first pick a problem structure. It's important to

note that your decision before each wave depends on three factors: the amount of money you have, the quantity of health potions you have, and the number of waves that have passed.

Define a suitable OPT for the problem, taking into consideration these three factors.

ii$.$ What is the goal of the problem, in terms of OPT?

iii. Write down the Bellman equation for OPT. Describe your equation.

iv$.$ What is the complexity of your algorithm? Justify your answer.