|
|
back to boardwhy always wa#10 Posted by abreto 18 Jan 2017 13:06 dp[n][k] = max{dp[n-1][k] or a[n], dp[n-1][k-1]} any hints?? thank you. Edited by author 18.01.2017 13:16 Re: why always wa#10 Posted by FlashKa 30 Aug 2018 16:03 3 2 7 6 1 Answer: 7 3 2 6 1 7 Answer: 7 Re: why always wa#10 because DP like this doesn't work lets consider next case 3 1 90 75 20 when we calculate last step we have: dp[3][1] = max(dp[2][1] or 20, dp[2][0]) now dp[2][1] = 90, dp[2][0] = 90 or 75 = 91 we are choosing max between (90 or 20) and 91, which is equal to 94 but this is incorrect answer correct answer is 75 or 20 = 95 |
|
|