Basketball exercise(editorial)

Revision en3, by zapdospops, 2019-10-11 21:22:44

1195C - Basketball Exercise

idea:zapdospops,KA_Rma submission 62187241

This is a standard dynamic programming problem

There are always 2 rows and in each row n students. The abstract idea of this problem is the zig-zag adding. Now there will be some case to skip the place in zig-zag and jump to another row. Pretty sure this will be an well optimized brute force method.

DYNAMIC PROGRAMMING:(Maximization Problem)

Lets take the 2 input arrays as a and b. Here we can construct an DP array (list(list)) of size (n+2) .Then now the same zig-zag with special DP condition is carried out. Variable i starts form 2 to n+2. For every DP[0][i] we we take max(DP[1][i-1],DP[1][i-2]) and add the current array value that is a[i-2] and simultaneously for every DP[1][i] we take max(DP[0][i-1],DP[0][i-2]) +b[i-2]. If you visualize each step with this equation we get an idea how the dynamic program store and use the previously stored values. pic2 DP[1][i] and DP[0][i]  pic

refer this easy dp problem for better understanding house-rober-leetcode.

Tags #dynamic programing

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English zapdospops 2019-10-11 21:22:44 442 Tiny change: '![Ex pictur' -> '[Ex pictur' (published)
en2 English zapdospops 2019-10-11 20:58:00 8
en1 English zapdospops 2019-10-11 20:56:56 1080 Initial revision (saved to drafts)