A robot starts at the top-left corner of an m × n grid and must reach the bottom-right corner. It can only move right or down. How many distinct paths exist?

Use dynamic programming where dp[i][j] reprseents the number of ways to reach cell (i, j) from the origin.

Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]

Base case: Initialize dp[0][1] = 1 to avoid boundary checks.

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[0][1] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};

2. Unique Paths II (With Obstacles)

Same as above, but some cells contain obstacles (marked as 1). Paths through obstacles are invalid.

If grid[i-1][j-1] == 1, then dp[i][j] = 0. Othewrise, apply the same recurrence.

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[0][1] = 1;
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (obstacleGrid[i - 1][j - 1] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

3. Maximum Jewel Value

Each cell contains a jewel with a positive value. Collect jewels while moving only right or down from top-left to bottom-right to maximize total value.

Define dp[i][j] as the maximum value achievable when reaching (i-1, j-1).

Transition: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1]

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(), n = frame[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};

4. Minimum Falling Path Sum

In an n × n matrix, start from any cell in the top row. At each step, move to the cell directly below or diagonally left/right in the next row. Find the path with minimum sum.

Define dp[i][j] as the minimum sum to reach row i, column j.

Transition: dp[i][j] = matrix[i-1][j-1] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])

Use padding with INT_MAX on sides to avoid index bounds.

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

5. Minimum Path Sum

Given a grid of non-negative integers, find the path from top-left to bottom-right with minimum sum, moving only right or down.

Define dp[i][j] as the minimum sum to reach cell (i-1, j-1).

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

Initialize with dp[0][1] = dp[1][0] = 0 to simplify boundary handling.

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = dp[1][0] = 0;
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};

6. Dungeon Game

A knight starts at the top-left of a dungeon grid. He must reach the bottom-right to rescue a princess. Each cell may add or subtract health. He dies if health ≤ 0. What’s the minimum initial health required?

This is a backward DP: define dp[i][j] as the minimum health needed to start from (i, j) and reach the end alive.

Transition: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])

Base: Set dp[m][n-1] = dp[m-1][n] = 1 to represent reaching the exit with 1 HP.

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int minHealth = min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = max(1, minHealth - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};