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(2^n) Recursion

  2. O(n^3) Brute Force

  3. O(n) Divide & Conquer

  4. O(n^2) DP
Reveal answer Fill a bubble to check yourself
A,D Correct answer
Explanation

This is the same minimum path sum problem - recursion explores all possible paths giving O(2^n) complexity, while dynamic programming with memoization achieves O(n^2) by avoiding recomputation. Divide & conquer is not applicable to this DP-optimized structure.

Keep practicing — related questions