CODBLND5 - Editorial

editorial
,
1

PROBLEM LINK: Practice

Author: Manzood Naqvi
Editorialist: Manzood Naqvi

DIFFICULTY:

MEDIUM

SOLUTION:

This is a somewhat standard Dynamic Programming problem that would typically serve as an introduction to the concept itself.
It might be useful to study at least the basics of Dynamic Programming to understand this editorial.

The problem can be solved by building another grid DP[n][m] alongside our current grid, A[n][m], where DP[i][j] stores the maximum possible sum that can be achieved by getting to position (i, j) on the grid.

For example, Each state in this DP grid can be stated as follows:

    DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + A[i][j]

Base Case: DP[0][0] = 0.

Once we have built this new grid, it will suffice to traverse the grid and find the maximum possible value of all positions on the DP grid where i + j == k, because those will end up being the final positions that the robot can stop at.

Time Complexity: O(n*m).

Code:

#include "bits/stdc++.h"
using namespace std;

int32_t main () {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        vector <vector <int>> A(n);
        vector <vector <long long>> DP(n);
        for (int i = 0; i < n; i++) {
            A[i].resize(m);
            DP[i].resize(m, 0);
            for (int j = 0; j < m; j++) {
                scanf("%d", &A[i][j]);
                DP[i][j] = A[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) DP[i][j] += DP[i][j-1];
                else if (j == 0) DP[i][j] += DP[i-1][j];
                else DP[i][j] += max(DP[i-1][j], DP[i][j-1]);
            }
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i + j == k) {
                    ans = max(DP[i][j], ans);
                }
            }
        }
        printf("%lld\n", ans);
    }
}