Basketball exercise(editorial)

Правка en1, от zapdospops, 2019-10-11 20:56:56

Problem statement 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.

If you still have doubt on this refer an easy DP problem.

Теги #dynamic programing

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский zapdospops 2019-10-11 21:22:44 442 Tiny change: '![Ex pictur' -> '[Ex pictur' (published)
en2 Английский zapdospops 2019-10-11 20:58:00 8
en1 Английский zapdospops 2019-10-11 20:56:56 1080 Initial revision (saved to drafts)