Problem $2.(10$ points$)$ Your friend comes up to you and claims to have found a more

efficient way to solve the rod cutting problem. This is your friend's strategy: you start

with a rod of length $n$ that you could sell for $p_n.$ Find the value of $k$ that maximizes the

payback you get from selling a rod of length $k$ and a rod of length $n-k,$ and make a

cut so that your payback is $p_k+p_{n-k}.$ If $k=0,$ this means you do not make cuts, so the

algorithms stops. But if $k>0,$ then you make a cut and then recursively apply the same

strategy to each sub$-$rod $($one of length $k$ and one of length $n-k).$ Provide a proof that

this is equivalent to the dynamic algorithm we previous saw for this problem, or give

an example to prove to your friend that this does not always provide an optimal solution.