Multiple choice technology

The complexity to solve this puzzel and technique to solve is Given a structure as below where n(i) is a number. n1 n2 n3 n4 n5 n6 . . . . You have two types of moves either move directly to immediate below or below right i.e. from n3 either to n5 or to n6. Sum the numbers along the way and find a path with minimum sum starting from the top to the bottom. e.g. 5 1 6 9 4 7 3 5 2 4 ans=12 path=5,1,4,2.

  1. O(n^3) Brute Force

  2. O(2^n) Recursion

  3. O(n^2) DP

  4. O(n) Divide & Conquer
Reveal answer Fill a bubble to check yourself
B,C Correct answer
Explanation

This minimum path sum problem can be solved by recursion (exponential O(2^n) by exploring all paths) or optimally by dynamic programming (O(n^2) using memoization). Brute force would be O(n^3) or worse, and divide & conquer doesn't apply to this DP structure.

Keep practicing — related questions