How to Use Dynamic Programming in this problem?

**Problem-**Riya is quite famous for her problem-solving skills in VESIT. When she was facing an interview for placement, a recruiter asked her this question :

Let’s consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line, three in the third line, etc. Develop a program which will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:

on each path the next number is located on the row below, more precisely either directly below or below and one place to the right.
Remember you cannot travel to the number which is below and one place to the left.

Please Explain…

1 Like

This is the sums in a triangle problem, You can try writing a naive recursive solution checking all the possibilities and then use memoization to cache results. :smiley:

1 Like

i am beginner,very weak at dp and recursion …please explain your approach and code,thanks a lot

As @tushkitripathi said, this is just the sums in a triangle problem. You can find the video editorial here - https://www.youtube.com/watch?v=ZSNWyyaxFYM&t=2s

1 Like

please suggest more basic qstns about dp and sources(for beginners)

These questions should help, also if you get stuck onto some question then search for that on google, there are various blogs for SPOJ problems on the internet. They will help.
:smiley:

Also, you might try starting with the problem bytelandian gold coins http://www.spoj.com/problems/COINS

This will clear your concepts about recursion and memoisation.

:smiley:

Here is a method to solve this problem

consider arr as the input array and ans as the array which will be required for making table.

let ans[i][j] represents sum that can be made by reaching cell i,j.

Now your answer would be max of all possible ans[i][j] which would be in last row.

ans[i][j]=arr[i][j]+max(ans[i-1][j],ans[i-1][j-1]).

1 Like

congo,welcome to new world of dp,please suggest more dp qstns and videos

edit-addition

1 Like

Google it. There are plenty of resources available there.

To be able to come up with a DP solution, you usually need to be good at recursion.
Here’s a good start to Recursion:
[Recursion I][1]
[Recursion II][2]
[1]: http://codingbat.com/java/Recursion-1
[2]: http://codingbat.com/java/Recursion-2

The above are in Java but you only need to know elementary functions like length of a string or an array, or how to compare two strings. Rest will be easy if you’re familiar with C++ or C syntax. Good luck!

1 Like

nice,i checked,this is such a great resource…thanks for suggesting this

1 Like

You’re welcome. :smiley:

i accepted your answer,enjoy

//