《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（36）太极图化路径 - 不同路径（组合数学优化）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的太极谷，谷中有一幅巨大的太极图，图中隐藏着无数路径。谷口有一块巨大的石碑，上面刻着一行文字：“欲破此谷，需以太极图之力，化路径，组合数学显真身。”

哪吒定睛一看，石碑上还有一行小字：“在一个m x n的网格中，从左上角到右下角的不同路径数为组合数C(m+n-2, m-1)。”哪吒心中一动，他知道这是一道关于计算不同路径数的难题，需要通过组合数学的优化来高效计算路径数。

暴力解法：太极图的初次尝试

哪吒心想：“要计算不同路径数，我可以逐个格子遍历。”他催动太极图之力，从网格的左上角开始，逐个格子移动，试图找到所有可能的路径。

int uniquePaths(int m, int n) {if (m == 1 || n == 1) return 1;return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}

哪吒成功地计算了不同路径数，但太极图的光芒却黯淡了下来。他意识到，这种方法虽然可行，但效率低下，尤其是当网格很大时，灵力消耗巨大。

C++语法点

在C++中，组合数学的优化涉及到递归和动态规划。以下是一些重要特性：

• 递归：

  • 递归函数会调用自身，直到满足终止条件。
  • 常用场景：
    • 组合数计算。
    • 路径数计算。

• 动态规划：

  • 动态规划通过将问题分解为子问题，并存储子问题的解来避免重复计算。
  • 常用操作：
    • 使用vector动态数组存储子问题的解。
    • 通过状态转移方程计算当前问题的解。

高阶优化：组合数学的智慧

哪吒元神中突然浮现金色铭文——「太极图化路径，组合数学显真身」。他意识到，可以通过组合数学的公式直接计算路径数，避免递归的重复计算。

哪吒决定使用组合数学的优化方法，通过计算组合数C(m+n-2, m-1)来得到路径数。通过这种方式，他成功地计算了不同路径数，而且灵力消耗大幅减少。

int uniquePaths(int m, int n) {int N = m + n - 2