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. DP[1][i] and DP[0][i]

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