Блог пользователя aroup

Автор aroup, 9 лет назад, По-английски

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.

Полный текст и комментарии »

Теги dp, uva
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор aroup, 9 лет назад, По-английски

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.

Полный текст и комментарии »

Теги #dp
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится