I am currently learning to solve dynamic programming problems, and I found this problem.
I am trying recursive approach,but I am finding it hard to determine the ending of recursive branches.
I am saving dp[index][right_length][left_length].
Their values are obtained from the maximum of int p1,p2,p3.
p1=recurse(index+1,right,left) ; // we can move to the next car
p2=1+recurse(index+1,right+arr[index],left); // we take it and add to the right
p3=1+recurse(index+1,right,left+arr[index]); // we take it and add to the left
I am wondering what the base cases might be.Any help can is appreciated.Thanks in advance.
The length of the ferry is up to 100 metres which is 10000 centimetres. You can't create an array [200][10000][10000].
bool dp[index][right_length]
dp[a][b] = can we pack first a cars that sum of lengths of cars on the right will be equal to b?