aroup's blog

By aroup, 7 years ago, In English

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.

Read more »

Tags dp, uva
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By aroup, 7 years ago, In English

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.

Read more »

Tags #dp
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it