📌 Part 1: How to Analyze the Question

🔍 Problem Summary

Given a grid of non-negative numbers:

• Start at top-left (0,0)
• Move only right or down
• Reach bottom-right
• Return the minimum path sum

🧭 Key Observations

1. Movement is restricted

• Only right → or down ↓
• No backtracking → no cycles

2. Each cell depends on previous cells

To reach (i, j), you must come from:

• Top → (i-1, j)
• Left → (i, j-1)

3. This signals Dynamic Programming

Look for:

• “minimum” → optimization problem
• repeated subproblems
• clear transition between states

💡 Define the State

dp[i][j] = minimum path sum to reach cell (i, j)

🔁 Transition

dp[i][j] = min(
dp[i-1][j], // from top
dp[i][j-1] // from left
) + grid[i][j]

🧱 Base Cases

Start:

dp[0][0] = grid[0][0]

First row:

dp[0][j] = dp[0][j-1] + grid[0][j]

First column:

dp[i][0] = dp[i-1][0] + grid[i][0]

🚀 Part 2: Standard DP Solution (2D)

💻 Code (TypeScript)

function minPathSum(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;

    const dp = Array.from({ length: m }, () => new Array(n).fill(0));

    dp[0][0] = grid[0][0];

    // first row
    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    // first column
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    // fill rest
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.min(
                dp[i - 1][j],
                dp[i][j - 1]
            ) + grid[i][j];
        }
    }

    return dp[m - 1][n - 1];
}

### ⏱ Complexity
- Time: O(m × n)
- Space: O(m × n)

🧩 Example

Grid:

1 3 1 1 5 1 4 2 1

DP table:

1 4 5 2 7 6 6 8 7

Final answer: **7**

## ⚡ Part 3: Space Optimization to O(n)
### 💡 Key Insight

Each cell only depends on:

current row left (dp[j-1])
previous row same column (dp[j] before update)

👉 So we can use 1D DP

### 🧠 State Definition
dp[j] = minimum path sum to reach current row's column j

### 🔁 Transition
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]

Where:

dp[j] = from top dp[j - 1] = from left

## 💻 Code (TypeScript)
```ts
function minPathSum(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;

    const dp = new Array(n).fill(0);

    // initialize first row
    dp[0] = grid[0][0];
    for (let j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }

    // process remaining rows
    for (let i = 1; i < m; i++) {
        // first column (only from top)
        dp[0] = dp[0] + grid[i][0];

        for (let j = 1; j < n; j++) {
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }

    return dp[n - 1];
}

⏱ Complexity

• Time: O(m × n)
• Space: O(n)

🔥 Key Takeaways

• Grid + restricted movement → DP
• Always define: dp[i][j] = answer for cell (i, j)
• Transition: from top OR left
• Space optimization works when: current state depends only on previous row + current row

🧭 Interview Mental Shortcut

If you see:

• grid
• right/down movement
• min/max path 👉 Instantly think:

dp[i][j] = min(top, left) + current