leetcode62：不同路径

题目链接

leetcode

题目描述

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。
机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
总共有多少条不同的路径？

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    动态规划

    状态表示：
        f(i, j) 表示从起点到(i, j)的路径总数，取 max
    状态计算：
        向下走一步，f(i, j) = f(i - 1, j) + f(i, j)
        向右走一步，f(i, j) = f(i, j - 1) + f(i, j)
    边界情况：
    	i == 0 || j == 0 时，dp[i][j] = 1

    时间复杂度：O(mn)
        其中 m 和 n 分别是网格的行数和列数。
    空间复杂度：O(mn)
*/
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m, vector<int>(n, 1));

        for (int i = 1; i < m; i ++) {
            for (int j = 1; j < n; j ++) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }

        return f[m - 1][n - 1];
    }
};

/*
    思路同上，优化空间

    由于 f[i][j] 只用到 f[i-1][j] 和 f[i][j-1]，
    所以可以使用滚动数组减小空间复杂度。

    时间复杂度：O(mn)
        其中 m 和 n 分别是网格的行数和列数。
    空间复杂度：O(n)
*/
class Solution_2 {
public:
    int uniquePaths(int m, int n) {
        vector<int> f(n, 1); // 初始化为 1
        // i, j 下标 从 1 开始
        for (int i = 1; i < m; i ++) {
            for (int j = 1; j < n; j ++) {
                f[j] = f[j] + f[j - 1];
            }
        }

        return f[n - 1];
    }
};

/*
    组合数学
    
    从网格左上角到网格右下角一共要走 m+n-2 步，
    在这些步数中，一共会向下走 m-1 步，向右走 n-1 步，
    经典的组合问题，结果是 C(n-1, m+n-2)。
    
    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution_3 {
public:
    int uniquePaths(int m, int n) {
        if (m > n) swap(m, n);

        double res = 1;
        for (int i = 1; i <= n - 1; i ++)
            res = res * (m - 1 + i) / i;

        return (int) res;
    }
};

int main() {
    Solution solution;
    vector<int> m_cases = { 3, 3 };
    vector<int> n_cases = { 7, 2 };

    for (int i = 0; i < m_cases.size(); i ++) {
        cout << "Input: m = " << m_cases[i] << ", n = " << n_cases[i] << endl;
        cout << "Output: " << solution.uniquePaths(m_cases[i], n_cases[i]) << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   动态规划：
       使用二维数组 dp，其中 dp[i][j] 表示从左上角到 (i, j) 的不同路径数量。
       初始化第一行和第一列的所有值为 1，因为只能沿着边界走。
       动态规划状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
   边界条件：
       如果 m 或 n 为 0，返回 0。
       如果 m 或 n 为 1，返回 1，因为只有一条路径。

   时间复杂度：O(mn)
       遍历整个 m * n 的网格，时间复杂度为 O(mn)。
   空间复杂度：O(mn)
       使用了一个大小为 m * n 的二维数组 dp，空间复杂度为 O(mn)。
*/
// uniquePaths 返回从左上角到右下角的不同路径数量
func uniquePaths(m int, n int) int {
    if m == 0 || n == 0 {
		return 0
	}

	// 初始化动态规划数组
	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
	}

	// 动态规划填表
	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]
}

/*
    状态转移方程：
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        这个方程表明，当前状态只依赖于左边和上边的状态。
    空间优化：
        由于当前状态只依赖于上一行和左边的值，可以使用一维数组来存储当前行的状态。
        在计算每一行时，更新一维数组的值。

    时间复杂度：O(mn)
    空间复杂度：O(n)
*/
func uniquePaths_1(m int, n int) int {
    if m == 0 || n == 0 {
		return 0
	}

	// 选择较小的维度作为一维数组的大小
	if m > n {
		m, n = n, m
	}

	// 初始化一维数组
	dp := make([]int, m)
	for i := range dp {
		dp[i] = 1
	}

	// 动态规划填表
	for i := 1; i < n; i ++ {
		for j := 1; j < m; j ++ {
			dp[j] += dp[j-1]
		}
	}

	return dp[m-1]
}

/*
    组合数学：
        从左上角到右下角的每条路径都由 m-1 次向下移动和 n-1 次向右移动组成。
        因此，问题可以转化为在 m+n-2 次移动中选择 n-1 次向右移动（或 m-1 次向下移动）的组合数。
    组合数公式：
        组合数 C(m+n-2, n-1) 表示从 m+n-2 个位置中选择 n-1 个位置的方法数。
        公式为：C(n, k) = C(n, n−k)，可以选择 k 和 n−k 中较小的一个来计算，以减少乘法次数。
		公式简化为：C(n, k) = n(n−1)(n−2)⋯(n−k+1) / k(k−1)(k−2)⋯1
    
    时间复杂度：O(n)
    空间复杂度：O(1)
*/
func uniquePaths_2(m int, n int) int {
	// 使用组合数公式计算
	return combination(m+n-2, n-1)
}

// combination 计算组合数 C(n, k)
func combination(n, k int) int {
	if k > n - k {
		k = n - k
	}
	result := 1
	for i := 1; i <= k; i ++ {
		result = result * (n - i + 1) / i
	}
	return result
}

func main() {
	// 测试用例
	testCases := []struct {
		m        int
		n        int
		expected int
	}{
		{
			m:        3,
			n:        7,
			expected: 28,
		},
		{
			m:        3,
			n:        2,
			expected: 3,
		},
		{
			m:        3,
			n:        3,
			expected: 6,
		},
	}

	for i, tc := range testCases {
		result := uniquePaths(tc.m, tc.n)
		fmt.Printf("Test Case %d, Input: m = %d, n = %d\n", i+1, tc.m, tc.n)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}