62. 不同路徑

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,0));// 2D vector的標準寫法 有些麻煩for (int i = 0; i < m; i++) dp[i][0] = 1; // 又忘記寫；了。。。for (int j = 0; j < n; j++) dp[0][j] = 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]; // 這里想漏了，一定要注意下是從0開始還是1開始的，如果是從0開就要-1}
};

拓展可以不用用二維數組去記錄，直接按循環的順序儲存一個一維滾動的數組就可以了。
這道題還有用數論的方法，思想是把這個問題轉化為排列組合問題。
二刷再來寫這兩種方法。

PS: 新手可以看看 我與GPT深入分析了一番為啥2D vector要這么定義。