走方格其实就是leetcode中的unique path

不同路径

leetcode中关于不同路径的题目有三道，在这里整理对比一下

• 起点和终点确定（左上角到右下角）且 前进方式只有向右和向下两种
  • 限制条件
    • 无障碍物 leetcode 62 [DP] 也就是本题
    • 有障碍物 leetcode 63 [DP]
• 起来和终点随机 且 前进方式为传统的四方向
  • 限制条件
    • 每个无障碍的方格都要走才算一条有效路径 leetcode 980 [DFS + 回溯]

完整版本 ： 不同路径

#include <iostream>

using namespace std;

const int N = 10;
int dp[N + 1][N + 1]; 

int uniquePath(int n, int m)
{
    dp[0][0] = 1;

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

    return dp[n][m];    

}

int main()
{
    int n, m;
    cin >> n >> m;

    cout << uniquePath(n, m) << endl;
    return 0;
}