Pascal Triangle Problem - Please help

Pascal’s triangle looks as follows:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
The first entry in a row is 1 and the last entry is 1 (except for the first row which contains only 1), and every other entry in Pascal’s triangle is equal to the sum of the two entries: the entry that is in the previous row and the same column, and the entry that is in the previous row and previous column.

(a) Give a recursive definition for the entry C[i, j] at row i and column j of Pascal’s triangle. Make sure that you distinguish the base case(s).

(b) Give a recursive algorithm to compute C[i, j], i > j > 1. Illustrate by drawing a diagram (tree) the steps that your algorithm performs to compute C[6, 4]. Does your algorithm perform overlapping computations?

(c) Use dynamic programming to design an O(n2) time algorithm that computes the first n rows in Pascal’s triangle. Does the dynamic programming algorithm performs better than the recursive
algorithm? Explain.

and your question is?

Quote:

---

Originally Posted by BlueBir86

Pascal’s triangle looks as follows:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
The first entry in a row is 1 and the last entry is 1 (except for the first row which contains only 1), and every other entry in Pascal’s triangle is equal to the sum of the two entries: the entry that is in the previous row and the same column, and the entry that is in the previous row and previous column.

(a) Give a recursive definition for the entry C[i, j] at row i and column j of Pascal’s triangle. Make sure that you distinguish the base case(s).

(b) Give a recursive algorithm to compute C[i, j], i > j > 1. Illustrate by drawing a diagram (tree) the steps that your algorithm performs to compute C[6, 4].

---

You could start from wiki to solve (a) and (b)

Quote:

---

Originally Posted by BlueBir86

(c) Use dynamic programming to design an O(n2) time algorithm that computes the first n rows in Pascal’s triangle. Does the dynamic programming algorithm performs better than the recursive
algorithm? Explain.

---

Being presented with the question it strikes me that,

recursion + memoization == dynamic programming

Remember you read it here first :)