PYTHON 3

PLEASE FOLLOW INSTRUCTIONS

#COMMENT STEPS :)

Problem

Given a triangle of integers, we want to find the path that has the largest sum going from the top to the bottom of the triangle. The way we go down the triangle is by moving down level by level, at each level having the choice to either go straight down to the integer directly below, or the integer below and to the right.

Consider the following triangle:

10

25 13

19 78 65

17 22 54 89

We start moving down the triangle from the top, with the node 10, where we have two options to choose from:

For the triangle given above, the maximum path from the top to the bottom is shown below:

Notice how the maximum path isn't necessarily always given by picking the element with the highest number at each step (see how we pick 15 over 19 when we are at 10 and trying to go from the first level to the second level).

Hint: consider solving this problem recursively:

Think about the base case. What's the simplest form of this problem that we can solve?

Think about how to articulate the two choices you have at each step

Think about how you're going to pick the best choice at each step

Compute this by completing the function maxPath(), which takes in a row R and a column C and a 2d-array triangle, and returns the maximum path from (R, C) to the bottom of the triangle. The top row in the triangle will have index 0, and the leftmost column will also have index 0.

1 triangLe-L 2 10], 3 C15,19], 4 [65,12,78], 5 [11,99,54,29 6 7 8 def maxPath(R, C, triangle)