I got stuck with this problem for quite a time now.It can be counted how many ways to make N with a number of coins.But I have no idea how to answer range query for this problem.

Problem Link

Any detailed hint of overall solution of this problem,it will be so much helpful.Thanks in advance.

I am currently learning to solve dynamic programming problems, and I found this problem.

Ferry Loading

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.