Problems that ask for a maximum or minimum sum along a path in a 2D grid can often be solved with dynamic programming where each cell’s optimal value depends on the best values of its predecessors. The recurrence follows a common pattern:

best(r, c) = candidate(r, c) + max/min(best(prev1), best(prev2), ...)

1. Triangle Path Maximization

Given a triangular matrix, move from the top to the bottom either down-left or down-right. Compute the largest total over any path.

1. Define table[i][j] as the best sum reaching row i, column j.
2. . The first row is a base case: table[0][0] = triangle[0][0].
3. For subsequent rows, a cell is reachable from above-left (i-1, j-1) or directly above (i-1, j).The recurrence is:table[i][j] = triangle[i][j] + max(table[i-1][j-1], table[i-1][j])`.

#include <stdio.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int main(void) {
    int rows;
    scanf("%d", &rows);
    int tri[rows][rows];
    int memo[rows][rows];

    for (int r = 0; r < rows; ++r)
        for (int c = 0; c <= r; ++c) {
            scanf("%d", &tri[r][c]);
            memo[r][c] = tri[r][c];
        }

    for (int r = 1; r < rows; ++r) {
        for (int c = 0; c <= r; ++c) {
            int from_left  = (c > 0)   ? memo[r-1][c-1] : 0;
            int from_right = (c < r)   ? memo[r-1][c]   : 0;
            int best_prev  = (c == 0)  ? from_right :
                             (c == r)  ? from_left  : MAX(from_left, from_right);
            memo[r][c] += best_prev;
        }
    }

    int answer = memo[rows-1][0];
    for (int c = 1; c < rows; ++c)
        if (memo[rows-1][c] > answer)
            answer = memo[rows-1][c];

    printf("%d\n", answer);
    return 0;
}

2. Minimum Passage Cost in a Square Grid

A matrix of size N×N. Start at top-left and finish at bottom-right, moving only right or down. Every cell has a cost; minimize the total sum along the path.

Initialization must be handled carefully: the first row can only be reached from the left, and the first column only from above. All other entries are filled using min(dp[row][col-1], dp[row-1][col]) + cost[row][col].

#include <stdio.h>
#include <limits.h>

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int main(void) {
    int n;
    scanf("%d", &n);
    int grid[n][n];

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &grid[i][j]);

    int f[n][n];
    f[0][0] = grid[0][0];

    for (int c = 1; c < n; ++c)
        f[0][c] = f[0][c-1] + grid[0][c];

    for (int r = 1; r < n; ++r)
        f[r][0] = f[r-1][0] + grid[r][0];

    for (int r = 1; r < n; ++r)
        for (int c = 1; c < n; ++c)
            f[r][c] = grid[r][c] + MIN(f[r][c-1], f[r-1][c]);

    printf("%d\n", f[n-1][n-1]);
    return 0;
}

3. Dual-Path Maximum Collection in a Matrix

Two routes traverse an N×N grid from top-left to bottom-right, only moving right or down. Each cell has a value that can be collected once if visited. This reqiures using a state that tracks both paths simultaneously. Because both paths advance by exactly one step per move, the sum of coordniates k = row1 + col1 = row2 + col2 is identical. We can895040op a 3D DP table: dp[k][r1][r2], where r1 and r2 are the current rows, and the columns are c1 = k - r1, c2 = k - r2.

The transition considers the four ways the previous step (k-1) could have been385:

• both moved down: dp[k-1][r1-1][r2-1]
• path 1 down, path 2 right: dp[k-1][r1-1][r2]
• path 1 right, path 2 down: dp[k-1][r1][r2-1]
• both moved right: dp[k-1][r1][r2]

encoding fetches from these780 the best and then adds the current cell(s) values. If both paths land on the same cell, its value is added only once.

#include <stdio.h>
#define MAX4(a, b, c, d) (                   \
    (a) > (b) ?                              \
        ((a) > (c) ? ((a) > (d) ? (a) : (d)) : ((c) > (d) ? (c) : (d))) \
    :                                         \
        ((b) > (c) ? ((b) > (d) ? (b) : (d)) : ((c) > (d) ? (c) : (d))) \
)

int main(void) {
    int n;
    scanf("%d", &n);
    int cell[n+1][n+1];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cell[i][j] = 0;

    int x, y, v;
    while (scanf("%d %d %d", &x, &y, &v) == 3 && (x || y || v))
        cell[x][y] = v;

    int max_k = 2 * n;
    int dp[max_k + 1][n + 1][n + 1];
    for (int k = 0; k <= max_k; ++k)
        for (int r1 = 0; r1 <= n; ++r1)
            for (int r2 = 0; r2 <= n; ++r2)
                dp[k][r1][r2] = 0;

    for (int k = 2; k <= max_k; ++k) {
        for (int r1 = 1; r1 <= n; ++r1) {
            int c1 = k - r1;
            if (c1 < 1 || c1 > n) continue;
            for (int r2 = 1; r2 <= n; ++r2) {
                int c2 = k - r2;
                if (c2 < 1 || c2 > n) continue;

                int gain = cell[r1][c1];
                if (r1 != r2 || c1 != c2)
                    gain += cell[r2][c2];

                int best = MAX4(
                    dp[k-1][r1-1][r2-1],
                    dp[k-1][r1][r2-1],
                    dp[k-1][r1-1][r2],
                    dp[k-1][r1][r2]
                );
                dp[k][r1][r2] = best + gain;
            }
        }
    }
    printf("%d\n", dp[max_k][n][n]);
    return 0;
}