1. The Problem
Given an `n x n` board where each cell `(i, j)` contains a gift of value `G[i, j]`, we need to find a path from the top-left cell `(0, 0)` to the bottom-right cell `(n-1, n-1)` that collects the maximum total value of gifts. The only allowed moves are right or down.
2. The Idea: Dynamic Programming
This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. The maximum value path to a cell `(i, j)` must pass through one of the adjacent cells from which it can be reached: either the cell above `(i-1, j)` or the cell to the left `(i, j-1)`.
Let `dp[i][j]` be the maximum value of gifts that can be collected on a path from `(0, 0)` to `(i, j)`. Our goal is to compute `dp[n-1][n-1]`.
- Base Case: The starting cell has no predecessors. `dp[0][0] = G[0, 0]`.
- Recurrence Relation: To get the maximum value at `dp[i][j]`, we take the value of the gift in that cell, `G[i, j]`, and add it to the maximum of the values from the cells we could have come from.
For cells in the first row (`i=0`), we can only move right: `dp[0][j] = G[0, j] + dp[0][j-1]`. For cells in the first column (`j=0`), we can only move down: `dp[i][0] = G[i, 0] + dp[i-1][0]`.
3. The Algorithm
- Create an `n x n` DP table, `dp`.
- Initialize the top-left corner: `dp[0][0] = G[0, 0]`.
- Fill the first row: For `j` from 1 to `n-1`, `dp[0][j] = G[0, j] + dp[0][j-1]`.
- Fill the first column: For `i` from 1 to `n-1`, `dp[i][0] = G[i, 0] + dp[i-1][0]`.
- Iterate through the rest of the grid, with `i` from 1 to `n-1` and `j` from 1 to `n-1`.
- Apply the recurrence: `dp[i][j] = G[i, j] + max(dp[i-1][j], dp[i][j-1])`.
- The maximal value is `dp[n-1][n-1]`.
4. Complexity Analysis
- Time Complexity: O(n²)
- We need to fill an `n x n` DP table. The calculation for each cell takes constant time. This requires iterating through all `n * n` cells once, resulting in O(n²) time complexity.
- Space Complexity: O(n²)
- We use an auxiliary `n x n` DP table to store the maximum values for subproblems. This requires O(n²) space. (This can be optimized to O(n) space since we only need the previous row to calculate the current row).