3596. 最小花费路径交替方向 I 🔒

题目描述

给定两个整数 m 和 n 分别表示一个网格的行数和列数。

进入单元格 (i, j) 的花费定义为 (i + 1) * (j + 1)。

路径始终从第 1 步进入单元格 (0, 0) 并支付入场花费开始。

在每一步，你移动到相邻的单元格，遵循交替的模式：

在 奇数次 移动，你必须向右方或下方移动。
在 偶数次 移动，你必须向左方或上方移动。

返回到达 (m - 1, n - 1) 的最小总花费。如果不可能到达，返回 -1。

示例 1：

输入：m = 1, n = 1

输出：1

解释：

你从单元格 (0, 0) 开始。
进入 (0, 0) 的花费是 (0 + 1) * (0 + 1) = 1。
由于你已经到达了目标，总花费为 1。

示例 2：

输入：m = 2, n = 1

输出：3

解释：

你从单元格 (0, 0) 开始，花费为 (0 + 1) * (0 + 1) = 1。
第 1 次移动（奇数次）：你可以向下移动到 (1, 0)，花费为 (1 + 1) * (0 + 1) = 2。
因此，总花费是 1 + 2 = 3。

提示：

1 <= m, n <= 10⁶

解法

方法一：脑筋急转弯

由于题目中给定的移动规则，实际上只有以下三种情况可以到达目标单元格：

行列数为 \(1 \times 1\) 的网格，花费为 \(1\)。
行数为 \(2\)，列数为 \(1\) 的网格，花费为 \(3\)。
行数为 \(1\)，列数为 \(2\) 的网格，花费为 \(3\)。

对于其他情况，无法到达目标单元格，返回 \(-1\)。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def minCost(self, m: int, n: int) -> int:
        if m == 1 and n == 1:
            return 1
        if m == 2 and n == 1:
            return 3
        if m == 1 and n == 2:
            return 3
        return -1

class Solution {
    public int minCost(int m, int n) {
        if (m == 1 && n == 1) {
            return 1;
        }
        if (m == 1 && n == 2) {
            return 3;
        }
        if (m == 2 && n == 1) {
            return 3;
        }
        return -1;
    }
}

class Solution {
public:
    int minCost(int m, int n) {
        if (m == 1 && n == 1) {
            return 1;
        }
        if (m == 1 && n == 2) {
            return 3;
        }
        if (m == 2 && n == 1) {
            return 3;
        }
        return -1;
    }
};

func minCost(m int, n int) int {
    if m == 1 && n == 1 {
        return 1
    }
    if m == 1 && n == 2 {
        return 3
    }
    if m == 2 && n == 1 {
        return 3
    }
    return -1
}

function minCost(m: number, n: number): number {
    if (m === 1 && n === 1) {
        return 1;
    }
    if (m === 1 && n === 2) {
        return 3;
    }
    if (m === 2 && n === 1) {
        return 3;
    }
    return -1;
}

3596. 最小花费路径交替方向 I 🔒

题目描述

解法

方法一：脑筋急转弯

评论