Luffy and Zoro

general
1

Luffy and Zoro are notorious pirates. They are infamous throughout Grand Line. One day they robbed Bank of Mariejois and looted a lot of beli (currency). this currency has different denominations. They want to divide the money in best possible way, so that difference in their shares is least. Help them and print the difference, otherwise they will fight.

2

By recursive approach there might be some sub problems which may overlap so memoization should be done.

K(3, 2) ---------> K(n, W)
/ \
/ \
K(2,2) K(2,1)
/ \ / \
/ \ /
K(1,2) K(1,1) K(1,1) K(1,0)
/ \ / \ /
/ \ / \ /
K(0,2) K(0,1) K(0,1) K(0,0) K(0,1) K(0,0)
So K(1,1) overlaps from above figure so again doing the same operation (i.e K(1,1) ) will increase time so Every Sub Problem should be memoized.

Complexity Using DP is O(n*W)

3

By recursive approach there might be some sub problems which may overlap so memoization should be done.

K(3, 2) ---------> K(n, W)

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp\

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp\
&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp K(2,2)&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspK(2,1)

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp\

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp\

&nbsp&nbsp&nbsp&nbsp&nbspK(1,2)&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspK(1,1)&nbsp&nbsp&nbsp&nbsp&nbsp&nbspK(1,1)&nbsp&nbsp&nbsp&nbsp&nbspK(1,0)

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp

&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp/&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp

K(0,2)K(0,1)&nbspK(0,1)K(0,0)K(0,1)K(0,0)

So K(1,1) overlaps from above figure so again doing the same operation (i.e K(1,1) ) will increase time so Every Sub Problem should be memoized.

Complexity Using DP is O(n*W)