3603. Minimum Cost Path with Alternating Directions II

You are given two integers m and n representing the number of rows and columns of a grid, respectively.

The cost to enter cell (i, j) is defined as (i + 1) * (j + 1).

You are also given a 2D integer array waitCost where waitCost[i][j] defines the cost to wait on that cell.

You start at cell (0, 0) at second 1.

At each step, you follow an alternating pattern:

• On odd-numbered seconds, you must move right or down to an adjacent cell, paying its entry cost.
• On even-numbered seconds, you must wait in place, paying waitCost[i][j].

Return the minimum total cost required to reach (m - 1, n - 1).

class Solution {
public:
    long long minCost(int n, int m, vector<vector<int>>& waitCost) {
        vector<vector<long long>> cost(n, vector<long long>(m, LLONG_MAX));
        cost[0][0] = 1;
        for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
            if(i + 1 < n) cost[i+1][j] = min(cost[i+1][j], waitCost[i+1][j] + cost[i][j] + (i + 2ll) * (j + 1ll));
            if(j + 1 < m) cost[i][j+1] = min(cost[i][j+1], waitCost[i][j+1] + cost[i][j] + (i + 1ll) * (j + 2ll));
        }

        return cost[n-1][m-1] - waitCost[n-1][m-1];
    }
};