Triangle (Min Path Sum)

🎯

Triangle (Min Path Sum)

mediumDPAmazonMicrosoft

Imagine you are climbing down a triangular mountain path where each step has a cost. You want to find the path from the top to the bottom with the minimum total cost.

💡 This problem is a classic example of grid-based dynamic programming where you must find an optimal path with minimum sum. Beginners often struggle because the triangle shape means each row has a different length, and the path choices depend on previous decisions, making brute force inefficient.

📋

Problem Statement

Given a triangle array, return the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. Formally, if you are on index i on the current row, you may move to either index i or i+1 on the next row.

1 ≤ number of rows ≤ 200Triangle elements are integers in the range [-10^4, 10^4]

💡

Example

Input"[[2],[3,4],[6,5,7],[4,1,8,3]]"

Output11

The minimum path is 2 → 3 → 5 → 1, which sums to 11.

• Triangle with only one row → output is that single element
• Triangle with negative numbers → path sum can be negative
• Triangle where all elements are equal → output is that element times number of rows
• Triangle with large values → test for integer overflow or performance

🔁

Why DP?

Why greedy fails:

A greedy approach that picks the minimum adjacent number at each step can fail because a locally minimal choice may lead to a suboptimal overall path. For example, choosing the smaller number at the second row might force a larger sum later.

DP state:

dp[i][j] represents the minimum path sum to reach element j in row i from the top.

Recurrence:dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])

The minimum path sum to position j in row i is the value at that position plus the minimum of the two possible positions above it.

⚠️

Common Mistakes

Not handling base case correctly in recursion

Stack overflow or incorrect results

✅ Add explicit base case when reaching last row to return value directly

Forgetting to memoize results in top-down DP

Solution still runs exponentially slow

✅ Use a cache to store and reuse computed results

Index out of bounds when accessing dp or triangle arrays

Runtime errors or crashes

✅ Ensure loops and recursive calls respect triangle row lengths

Updating dp array in wrong order in bottom-up approach

Incorrect results due to overwritten values

✅ Iterate from bottom row upwards and update dp carefully

Using extra space unnecessarily in bottom-up approach

Higher memory usage than needed

✅ Use a single 1D dp array updated in place

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's recursive structure and why naive recursion is inefficient due to repeated calculations.

Intuition

At each position, recursively explore both possible moves down the triangle and choose the minimum path sum.

Algorithm

1. Start at the top of the triangle (row 0, index 0).
2. Recursively compute the minimum path sum for the two adjacent positions in the next row.
3. Return the current value plus the minimum of the two recursive calls.
4. The base case is when we reach the last row, where we return the value itself.

💡 The recursion tree grows exponentially because each call branches into two, making it hard to track without memoization.

Recurrence:minPath(i,j) = triangle[i][j] + min(minPath(i+1,j), minPath(i+1,j+1))

</>

Code

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    def dfs(i, j):
        if i == len(triangle) - 1:
            return triangle[i][j]
        left = dfs(i + 1, j)
        right = dfs(i + 1, j + 1)
        return triangle[i][j] + min(left, right)

    return dfs(0, 0)

# Example usage
if __name__ == "__main__":
    tri = [[2],[3,4],[6,5,7],[4,1,8,3]]
    print(minimumTotal(tri))  # Output: 11

Line Notes

def dfs(i, j):Defines recursive helper to compute min path sum from position (i,j)

if i == len(triangle) - 1:Base case: last row reached, return value directly

left = dfs(i + 1, j)Recurse to the adjacent number directly below

right = dfs(i + 1, j + 1)Recurse to the adjacent number diagonally below

return triangle[i][j] + min(left, right)Add current value to minimum of two recursive paths

import java.util.*;

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return dfs(triangle, 0, 0);
    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size() - 1) {
            return triangle.get(i).get(j);
        }
        int left = dfs(triangle, i + 1, j);
        int right = dfs(triangle, i + 1, j + 1);
        return triangle.get(i).get(j) + Math.min(left, right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> tri = new ArrayList<>();
        tri.add(Arrays.asList(2));
        tri.add(Arrays.asList(3,4));
        tri.add(Arrays.asList(6,5,7));
        tri.add(Arrays.asList(4,1,8,3));
        System.out.println(sol.minimumTotal(tri)); // 11
    }
}

Line Notes

public int minimumTotal(List<List<Integer>> triangle)Entry point calling recursive helper

if (i == triangle.size() - 1)Base case: last row reached

int left = dfs(triangle, i + 1, j);Recurse down to left adjacent

int right = dfs(triangle, i + 1, j + 1);Recurse down to right adjacent

return triangle.get(i).get(j) + Math.min(left, right);Add current value to min of recursive results

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int dfs(const vector<vector<int>>& triangle, int i, int j) {
        if (i == triangle.size() - 1) return triangle[i][j];
        int left = dfs(triangle, i + 1, j);
        int right = dfs(triangle, i + 1, j + 1);
        return triangle[i][j] + min(left, right);
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        return dfs(triangle, 0, 0);
    }
};

int main() {
    Solution sol;
    vector<vector<int>> tri = {{2},{3,4},{6,5,7},{4,1,8,3}};
    cout << sol.minimumTotal(tri) << endl; // 11
    return 0;
}

Line Notes

int dfs(const vector<vector<int>>& triangle, int i, int j)Recursive helper to compute min path sum

if (i == triangle.size() - 1) return triangle[i][j];Base case: last row reached

int left = dfs(triangle, i + 1, j);Recurse to left adjacent below

int right = dfs(triangle, i + 1, j + 1);Recurse to right adjacent below

return triangle[i][j] + min(left, right);Add current value to minimum of recursive calls

function minimumTotal(triangle) {
    function dfs(i, j) {
        if (i === triangle.length - 1) return triangle[i][j];
        const left = dfs(i + 1, j);
        const right = dfs(i + 1, j + 1);
        return triangle[i][j] + Math.min(left, right);
    }
    return dfs(0, 0);
}

// Example usage
const tri = [[2],[3,4],[6,5,7],[4,1,8,3]];
console.log(minimumTotal(tri)); // 11

Line Notes

function dfs(i, j)Recursive helper function for min path sum

if (i === triangle.length - 1) return triangle[i][j];Base case: last row reached

const left = dfs(i + 1, j);Recurse down left adjacent

const right = dfs(i + 1, j + 1);Recurse down right adjacent

return triangle[i][j] + Math.min(left, right);Add current value to min of recursive calls

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each step branches into two recursive calls, leading to exponential growth in calls.

💡 For n=15 rows, this means over 32,000 calls, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency.

Intuition

Store results of recursive calls in a cache so that repeated calls return instantly instead of recomputing.

Algorithm

1. Initialize a cache (2D array) to store minimum path sums for each position.
2. Modify the recursive function to check the cache before computing.
3. If cached, return the stored value; otherwise compute and store it.
4. Return the cached result for the top position.

💡 Memoization transforms exponential recursion into polynomial time by eliminating duplicate work.

Recurrence:dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])

</>

Code

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    n = len(triangle)
    memo = [[None]*len(row) for row in triangle]

    def dfs(i, j):
        if i == n - 1:
            return triangle[i][j]
        if memo[i][j] is not None:
            return memo[i][j]
        left = dfs(i + 1, j)
        right = dfs(i + 1, j + 1)
        memo[i][j] = triangle[i][j] + min(left, right)
        return memo[i][j]

    return dfs(0, 0)

# Example usage
if __name__ == "__main__":
    tri = [[2],[3,4],[6,5,7],[4,1,8,3]]
    print(minimumTotal(tri))  # Output: 11

Line Notes

memo = [[None]*len(row) for row in triangle]Initialize cache with None to mark uncomputed states

if memo[i][j] is not None:Return cached result if available to avoid recomputation

memo[i][j] = triangle[i][j] + min(left, right)Store computed minimum path sum in cache

return memo[i][j]Return cached or newly computed result

import java.util.*;

public class Solution {
    private Integer[][] memo;

    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        memo = new Integer[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new Integer[triangle.get(i).size()];
        }
        return dfs(triangle, 0, 0);
    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size() - 1) {
            return triangle.get(i).get(j);
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        int left = dfs(triangle, i + 1, j);
        int right = dfs(triangle, i + 1, j + 1);
        memo[i][j] = triangle.get(i).get(j) + Math.min(left, right);
        return memo[i][j];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> tri = new ArrayList<>();
        tri.add(Arrays.asList(2));
        tri.add(Arrays.asList(3,4));
        tri.add(Arrays.asList(6,5,7));
        tri.add(Arrays.asList(4,1,8,3));
        System.out.println(sol.minimumTotal(tri)); // 11
    }
}

Line Notes

memo = new Integer[n][];Initialize memo array with nulls to mark uncomputed states

if (memo[i][j] != null)Return cached result if available

memo[i][j] = triangle.get(i).get(j) + Math.min(left, right);Store computed minimum path sum

return memo[i][j];Return cached or computed result

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
    vector<vector<int>> memo;
public:
    int dfs(const vector<vector<int>>& triangle, int i, int j) {
        if (i == triangle.size() - 1) return triangle[i][j];
        if (memo[i][j] != INT_MAX) return memo[i][j];
        int left = dfs(triangle, i + 1, j);
        int right = dfs(triangle, i + 1, j + 1);
        memo[i][j] = triangle[i][j] + min(left, right);
        return memo[i][j];
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        memo.assign(n, vector<int>(n, INT_MAX));
        return dfs(triangle, 0, 0);
    }
};

int main() {
    Solution sol;
    vector<vector<int>> tri = {{2},{3,4},{6,5,7},{4,1,8,3}};
    cout << sol.minimumTotal(tri) << endl; // 11
    return 0;
}

Line Notes

memo.assign(n, vector<int>(n, INT_MAX));Initialize memo with sentinel INT_MAX to mark uncomputed

if (memo[i][j] != INT_MAX) return memo[i][j];Return cached result if computed

memo[i][j] = triangle[i][j] + min(left, right);Store computed minimum path sum

return memo[i][j];Return cached or computed result

function minimumTotal(triangle) {
    const n = triangle.length;
    const memo = Array.from({length: n}, (v, i) => Array(triangle[i].length).fill(null));

    function dfs(i, j) {
        if (i === n - 1) return triangle[i][j];
        if (memo[i][j] !== null) return memo[i][j];
        const left = dfs(i + 1, j);
        const right = dfs(i + 1, j + 1);
        memo[i][j] = triangle[i][j] + Math.min(left, right);
        return memo[i][j];
    }

    return dfs(0, 0);
}

// Example usage
const tri = [[2],[3,4],[6,5,7],[4,1,8,3]];
console.log(minimumTotal(tri)); // 11

Line Notes

const memo = Array.from({length: n}, (v, i) => Array(triangle[i].length).fill(null));Initialize memo array with nulls

if (memo[i][j] !== null) return memo[i][j];Return cached result if available

memo[i][j] = triangle[i][j] + Math.min(left, right);Store computed minimum path sum

return memo[i][j];Return cached or computed result

⏱

Complexity

TimeO(n^2)

SpaceO(n^2) for memo and recursion stack

Each subproblem is computed once and stored, reducing exponential calls to polynomial.

💡 For n=200 rows, this means about 40,000 computations, which is efficient enough.

Interview Verdict: Accepted

Memoization makes the solution efficient and acceptable for interviews.

🧠

Bottom-Up DP (Tabulation)

💡 This approach builds the solution from the bottom row up, avoiding recursion and making the process iterative and clear.

Intuition

Start from the last row and iteratively compute minimum path sums for each upper row by adding the current value to the minimum of the two adjacent values below.

Algorithm

1. Initialize a dp array as a copy of the last row of the triangle.
2. Iterate from the second last row up to the top row.
3. For each element, update dp[j] as triangle[i][j] plus min(dp[j], dp[j+1]).
4. After processing the top row, dp[0] contains the minimum path sum.

💡 This approach uses a single dp array updated in place, making it space efficient and easy to understand.

Recurrence:dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])

</>

Code

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    dp = triangle[-1][:]
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[i])):
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
    return dp[0]

# Example usage
if __name__ == "__main__":
    tri = [[2],[3,4],[6,5,7],[4,1,8,3]]
    print(minimumTotal(tri))  # Output: 11

Line Notes

dp = triangle[-1][:]Initialize dp with last row values as base case

for i in range(len(triangle) - 2, -1, -1):Iterate from second last row up to top

for j in range(len(triangle[i])):Iterate over elements in current row

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])Update dp[j] with current value plus min of two below

import java.util.*;

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> tri = new ArrayList<>();
        tri.add(Arrays.asList(2));
        tri.add(Arrays.asList(3,4));
        tri.add(Arrays.asList(6,5,7));
        tri.add(Arrays.asList(4,1,8,3));
        System.out.println(sol.minimumTotal(tri)); // 11
    }
}

Line Notes

int[] dp = new int[n];Create dp array to store min path sums for last row

dp[i] = triangle.get(n - 1).get(i);Initialize dp with last row values

for (int i = n - 2; i >= 0; i--)Iterate from second last row up to top

dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);Update dp[j] with current value plus min of two below

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> dp = triangle.back();
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> tri = {{2},{3,4},{6,5,7},{4,1,8,3}};
    cout << sol.minimumTotal(tri) << endl; // 11
    return 0;
}

Line Notes

vector<int> dp = triangle.back();Initialize dp with last row values

for (int i = n - 2; i >= 0; i--)Iterate from second last row up to top

for (int j = 0; j <= i; j++)Iterate over elements in current row

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);Update dp[j] with current value plus min of two below

function minimumTotal(triangle) {
    let dp = triangle[triangle.length - 1].slice();
    for (let i = triangle.length - 2; i >= 0; i--) {
        for (let j = 0; j < triangle[i].length; j++) {
            dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
        }
    }
    return dp[0];
}

// Example usage
const tri = [[2],[3,4],[6,5,7],[4,1,8,3]];
console.log(minimumTotal(tri)); // 11

Line Notes

let dp = triangle[triangle.length - 1].slice();Copy last row into dp array

for (let i = triangle.length - 2; i >= 0; i--)Iterate from second last row up to top

for (let j = 0; j < triangle[i].length; j++)Iterate over elements in current row

dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);Update dp[j] with current value plus min of two below

⏱

Complexity

TimeO(n^2)

SpaceO(n)

We process each element once and use a single dp array of size n.

💡 For n=200 rows, this means about 40,000 operations and only 200 space used.

Interview Verdict: Accepted

This is the preferred approach in interviews due to clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Bottom-up DP with space optimization is the best choice for interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(n^2)	O(n^2) memo + O(n) recursion stack	Possible but less likely	Yes	Good to mention and code if comfortable
3. Bottom-Up DP (Tabulation)	O(n^2)	O(n)	No	Yes	Preferred approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force recursive approach to show understanding of the problem structure.Introduce memoization to optimize recursion and avoid repeated work.Present the bottom-up DP approach for iterative clarity and space optimization.Write clean code and test with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of recursion, dynamic programming concepts, optimization techniques, and ability to write clean, bug-free code.

Common Follow-ups

• Can you optimize space usage further? → Use 1D dp array as shown in bottom-up approach.
• What if the triangle is very large? → Discuss time and space complexity and possible pruning.

💡 Follow-ups often test your ability to optimize space and handle large inputs efficiently.

🔍

Pattern Recognition

When to Use

1) Problem involves grid or triangle structure; 2) Need to find min/max path sum; 3) Choices depend on adjacent positions; 4) Overlapping subproblems exist.

Signature Phrases

'minimum path sum from top to bottom''move to adjacent numbers on the row below'

NOT This Pattern When

Problems that require global path sums without adjacency constraints or that use greedy approaches exclusively.

Similar Problems

Minimum Path Sum - similar grid DP with fixed directionsUnique Paths II - grid DP with obstacles

Practice

1. Consider the following Python code implementing the space-optimized DP solution for Maximal Square. Given the input matrix below, what is the final returned value? Matrix: [ ["1", "0", "1"], ["1", "1", "1"], ["1", "1", "0"] ]

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    dp = [0] * (cols + 1)
    max_side = 0
    prev = 0
    for i in range(rows):
        for j in range(1, cols + 1):
            temp = dp[j]
            if matrix[i][j-1] == '1':
                dp[j] = 1 + min(dp[j], dp[j-1], prev)
                max_side = max(max_side, dp[j])
            else:
                dp[j] = 0
            prev = temp
    return max_side * max_side

easy

A. 0

B. 4

C. 9

D. 1

Solution

1. Step 1: Trace dp array updates for each row

   Row 0: dp updates to [0,1,0,1], max_side=1; Row 1: dp updates to [0,1,1,1], then dp[3]=1+min(1,1,1)=2, max_side=2; Row 2: dp updates to [0,1,2,0], max_side remains 2.

2. Step 2: Calculate final area

   max_side=2, so area = 2*2 = 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Max square side 2 -> area 4 [OK]

Hint: Track dp updates row-wise to find max side [OK]

Common Mistakes:

• Off-by-one in indexing dp array
• Confusing prev and temp updates
• Returning max_side instead of area

2. You are given an array of piles of stones. Two players alternately take stones from either end of the array, aiming to maximize their total stones. Both players play optimally. Which algorithmic approach guarantees finding the maximum difference in stones the first player can achieve over the second?

easy

A. Dynamic programming using interval-based state representation

B. Sorting piles and picking stones from the largest piles first

C. Simple recursion without memoization

D. Greedy approach picking the largest pile at each turn

Solution

1. Step 1: Understand the problem structure

   The problem involves two players picking from ends of an array, which naturally forms intervals that shrink over time.

2. Step 2: Identify the suitable algorithmic pattern

   Dynamic programming with intervals captures the state (i, j) representing the current subarray, allowing optimal substructure and overlapping subproblems to be exploited.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Interval DP is the classic approach for two-player games on arrays [OK]

Hint: Two-player games on arrays -> interval DP [OK]

Common Mistakes:

• Thinking greedy works because largest pile seems best
• Using recursion without memoization causes TLE

3. Consider the following snippet from the optimal Zuma Game solution. Given board = "WRRBBW" and hand = "RB", what is the return value of findMinStep(board, hand)?

easy

A. 2

B. -1

C. 3

D. 1

Solution

1. Step 1: Trace initial calls with board="WRRBBW" and hand="RB"

   Hand has 1 R and 1 B. The board requires more balls to clear groups of 3, but hand is insufficient to clear all.

2. Step 2: Check if any insertion sequence clears board

   Trying to insert R or B balls to form groups of 3 fails due to insufficient balls; no sequence clears the board fully.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Return -1 indicates no solution with given hand [OK]

Hint: Insufficient hand balls cause no solution -> -1 [OK]

Common Mistakes:

• Assuming partial removals suffice to clear board
• Miscounting balls needed for group removal
• Forgetting to restore hand counts after recursion

4. The following code attempts to compute the number of unique paths in an m x n grid using a space-optimized DP approach:

def uniquePaths(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] = dp[j] + dp[j]
    return dp[-1]

What is the bug in this code?

medium

A. Line 3 should start loop from 0 instead of 1

B. Line 4 incorrectly doubles dp[j] instead of adding dp[j-1]

C. Line 5 should return dp[0] instead of dp[-1]

D. Line 2 initializes dp with wrong size

Solution

1. Step 1: Analyze inner loop update

   Line 4 updates dp[j] by adding dp[j] to itself, doubling the value instead of adding dp[j-1].

2. Step 2: Identify correct update

   The correct update is dp[j] += dp[j - 1] to accumulate paths from left and top cells.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Doubling dp[j] breaks path count logic -> bug at line 4 [OK]

Hint: Check dp update uses dp[j-1], not dp[j] twice [OK]

Common Mistakes:

• Using dp[j] + dp[j] instead of dp[j] + dp[j-1]
• Off-by-one errors in loops

5. Suppose the problem is modified so that you can move right, down, or diagonally down-right, still avoiding obstacles. Which of the following changes to the space-optimized DP approach correctly accounts for the new diagonal move?

hard

A. Modify dp[j] += dp[j-1] to dp[j] += dp[j-1] + dp[j] without extra storage.

B. Use a 2D dp array where dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], updating in row-major order.

C. Add dp[j-1] and dp[j] plus dp[j-1] from previous row, requiring a 2D dp array to track diagonal paths.

D. Keep 1D dp array but add dp[j-1] twice to account for diagonal moves.

Solution

1. Step 1: Understand diagonal dependency

   Diagonal move depends on dp[i-1][j-1], which cannot be tracked with only 1D dp array updated in-place.

2. Step 2: Correct approach

   Use 2D dp array to store counts for all cells, updating dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], ensuring all dependencies are available.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Diagonal requires previous row and previous column info simultaneously [OK]

Hint: Diagonal moves require 2D dp to track previous row and column [OK]

Common Mistakes:

• Trying to reuse 1D dp without extra storage
• Double counting paths
• Ignoring diagonal dependency