LeetCode-in-Java

3603. Minimum Cost Path with Alternating Directions II

Medium

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:

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

Example 1:

Input: m = 1, n = 2, waitCost = [[1,2]]

Output: 3

Explanation:

The optimal path is:

Thus, the total cost is 1 + 2 = 3.

Example 2:

Input: m = 2, n = 2, waitCost = [[3,5],[2,4]]

Output: 9

Explanation:

The optimal path is:

Thus, the total cost is 1 + 2 + 2 + 4 = 9.

Example 3:

Input: m = 2, n = 3, waitCost = [[6,1,4],[3,2,5]]

Output: 16

Explanation:

The optimal path is:

Thus, the total cost is 1 + 2 + 1 + 4 + 2 + 6 = 16.

Constraints:

Solution

public class Solution {
    public long minCost(int m, int n, int[][] waitCost) {
        long[] dp = new long[n];
        dp[0] = 1L;
        for (int j = 1; j < n; j++) {
            long entry = j + 1L;
            long wait = waitCost[0][j];
            dp[j] = dp[j - 1] + entry + wait;
        }
        for (int i = 1; i < m; i++) {
            long entry00 = i + 1L;
            long wait00 = waitCost[i][0];
            dp[0] = dp[0] + entry00 + wait00;
            for (int j = 1; j < n; j++) {
                long entry = (long) (i + 1) * (j + 1);
                long wait = waitCost[i][j];
                long fromAbove = dp[j];
                long fromLeft = dp[j - 1];
                dp[j] = Math.min(fromAbove, fromLeft) + entry + wait;
            }
        }
        return dp[n - 1] - waitCost[m - 1][n - 1];
    }
}