Need Guidance for Kick Start Round A 2020 - PLATES

help
,
1

I know we have to use dynamic programming but i wasn’t able to figure out the solution. Had read the analysis but it was a bit confusing. Can someone explain me the core algorithm behind it?

The link to problem: Kick Start - Google’s Coding Competitions

Peace! :slight_smile:

Ps. I don’t want the code. I want to know the algorithm. Thank You

1 Like
2

Let dp[i][j] denote the maximum beauty of j plates from the first i stacks. Then choose the no. Of plates in combination with each previous dp state
So dp[i][j] =max(dp[i-1][j-x] + sum[i][x]) where sum[i][x] denotes the beauty of the first x plates in stack i.

3 Likes