不同路径

题目要求

这是一个经典的组合问题，可以用动态规划（Dynamic Programming）来解决。题目要求我们计算一个机器人从一个 m x n 网格的左上角（起点）移动到右下角（终点）的不同路径的总数。机器人在任何时刻只能向下或者向右移动。

解题思路

为了解决这个问题，我们可以采用以下步骤：

理解问题：首先，我们需要理解机器人每次只能向下或向右移动意味着什么。这意味着如果机器人在某个位置，它只能从它的上方或左方到达那里。
初始化边界：在网格的顶部行和最左侧列，机器人只有一种方式到达每个点（要么一直向右，要么一直向下）。因此，这些位置的路径数都是 1。
填充网格：对于网格中的其他点，机器人可以从上方或左方到达。因此，到达该点的路径总数是到达它上方格子的路径数加上到达它左方格子的路径数。
动态规划方程：我们可以定义一个二维数组 dp，其中 dp[i][j] 表示到达网格中第 i 行第 j 列的路径总数。状态转移方程为：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
计算结果：按照从上到下，从左到右的顺序填充这个 dp 数组。最终，dp[m-1][n-1] 就是我们要找的答案，即到达网格右下角的路径总数。
优化空间复杂度：如果需要，我们可以只用一个一维数组来优化空间复杂度，因为更新 dp 数组的时候，我们只需要知道当前行的上一行的状态。

通过以上步骤，我们可以不使用递归（会导致大量重复计算），而是使用动态规划的方法，有效地计算出不同的路径总数。

Golang 版本

package main

import "fmt"

func uniquePaths(m int, n int) int {
    // 创建一个二维切片来存储中间结果
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    // 初始化第一行和第一列的值为1，因为只有一条路径可以到达
    for i := 0; i < m; i++ {
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }

    // 从(1,1)开始，使用状态转移方程填充dp表
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }

    // 返回到达右下角的路径总数
    return dp[m-1][n-1]
}

func main() {
    m, n := 3, 7
    fmt.Println("Total unique paths:", uniquePaths(m, n))
}

这段代码定义了一个uniquePaths函数，它接受两个整数m和n作为输入，分别代表网格的行数和列数。然后，它使用动态规划的方法来计算从网格的左上角到右下角的唯一路径数，并在main函数中调用这个函数并打印结果。

C++版本

#include <iostream>
#include <vector>

int uniquePaths(int m, int n) {
    std::vector<std::vector<int>> dp(m, std::vector<int>(n, 1)); // 初始化dp数组，所有值为1

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 状态转移方程
        }
    }

    return dp[m - 1][n - 1]; // 返回右下角的路径数
}

int main() {
    int m = 3, n = 7;
    std::cout << "Total unique paths: " << uniquePaths(m, n) << std::endl;
    return 0;
}

这段 C++代码实现了与 Golang 版本相同的功能。它定义了一个uniquePaths函数，使用动态规划来计算网格中的唯一路径数，并在main函数中测试这个函数。

Python 版本

def unique_paths(m, n):
    # 初始化dp表，所有值为1
    dp = [[1] * n for _ in range(m)]

    # 使用状态转移方程填充dp表
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    # 返回到达右下角的路径总数
    return dp[-1][-1]

# 测试函数
if __name__ == "__main__":
    m, n = 3, 7
    print(f"Total unique paths: {unique_paths(m, n)}")

这段 Python 代码实现了与前面 Golang 和 C++版本相同的逻辑。它定义了一个unique_paths函数来计算网格中的唯一路径数，并在脚本的主部分中测试了这个函数。

Java 版本

public class UniquePaths {
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // 初始化第一行和第一列
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        // 填充剩余的dp表
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        // 返回右下角的值
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int m = 3, n = 7;
        System.out.println("Total unique paths: " + uniquePaths(m, n));
    }
}

这段 Java 代码定义了一个UniquePaths类，其中包含了一个uniquePaths方法来计算网格中的唯一路径数。main方法用于测试这个功能。

Rust 版本

fn unique_paths(m: i32, n: i32) -> i32 {
    let mut dp = vec![vec![1; n as usize]; m as usize];

    for i in 1..m as usize {
        for j in 1..n as usize {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    dp[(m - 1) as usize][(n - 1) as usize]
}

fn main() {
    let m = 3;
    let n = 7;
    println!("Total unique paths: {}", unique_paths(m, n));
}

这段 Rust 代码实现了一个unique_paths函数，它计算从网格的左上角到右下角的不同路径的总数。在main函数中，它测试了这个函数并打印出结果。

总结

上述代码示例展示了如何使用动态规划算法来解决机器人从网格左上角到右下角的不同路径问题。无论是在 Golang、C++、Python 还是 Java 和 Rust 语言中，核心思想都是相同的：

初始化一个二维数组（或切片、向量等），其大小与网格的行数和列数相同。这个数组用于存储到达每个格子的路径数。
将数组的第一行和第一列的所有元素设置为 1，因为到达第一行和第一列的任何格子都只有一条路径（只能一直向右或一直向下移动）。
对于数组中的其他元素，应用状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。这表示到达当前格子的路径数等于到达其正上方格子的路径数加上到达其左侧格子的路径数。
最后，数组的最后一个元素（dp[m-1][n-1]）即为到达网格右下角的总路径数。

这种方法避免了递归和重复计算，提供了一种高效的解决方案。每种语言的实现都遵循了这个算法框架，只是在语法和数据结构的使用上有所不同。

hot-100