**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.
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.
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]: CodingBat Java Recursion-1
[2]: CodingBat 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!
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.
