Problem 1: Triangle Minimum Path Sum

Given a triangular array triangle with n rows, find the minimum path sum from the top to the bottom.

• You start at triangle[0][0].
• From row i, column j, you may move to row i+1 at column j or j+1.
• Return the minimum possible sum along any valid top-to-bottom path.

Input: A list of lists, where row i has length i+1.

Output: An integer (or numeric) minimum path sum.

Constraints (typical): 1 <= n <= 2000, values may be negative/positive.

Problem 2: Two Dice Stopping Problem + Monte Carlo Simulation

There are two fair dice:

• Die A has faces {1,2,3,4,5} (a 5-sided die).
• Die B has faces {1,2,3,4,5,6} (a 6-sided die).

The experiment proceeds in rounds. In each round, you roll both dice once.

• The process stops at the first round where at least one die shows 1.
• In the stopping round:
  • Die A wins if A=1 and B≠1.
  • Die B wins if B=1 and A≠1.
  • It is a tie if A=1 and B=1.

Answer the following:

1. What is the probability that the 5-sided die (Die A) wins?
2. What is the expected number of rounds until the process stops?
3. Implement a Monte Carlo simulation to estimate (1) and (2), and discuss how many trials you would run to get a stable estimate.