题意：
给定 m 行 n 列的网格，机器人从左上角( 0 , 0 )出发，每次只可以向左或向下走一步，走到右下角位置，问有多少种走法？
输入样例:
2 3
输出样例:
3
确定末状态:
在某位置 ( x , y ) ，可以化为子问题由 ( x-1, y )向下走一步,或由 ( x, y-1 )向右走一步,这两个子问题相加就是走到 ( x , y )的方法
状态方程:
dp[ i ][ j ]=dp[ i-1][ j ]+dp[ i ][ j-1 ]
初始状态和边界情况：
初始状态及边界情况，在格子( i,0) 和( 0 , j )的地方都只有一种情况到达，即 i==0或 j==0 dp[ i ][ j ]=1
#include<iostream> #include<string.h> #include<math.h> using namespace std; int n,m,v; int ans; int mod=1e9+7; int dp[105][105]; bool vis[105]; int main(){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(i==0||j==0){ dp[i][j]=1; } else{ dp[i][j]=dp[i-1][j]+dp[i][j-1]; //因为考虑了 i=0 和 j=0 的情况，则 i-1和 j-1就不存在越界了 } } } cout<<dp[n-1][m-1]; return 0; }
更进一步的，给k个格子，使这些格子有障碍，不能到达这些格子，问这种情况下到右下角的总数
输入样例：
3 3 1
1 1
输出样例：
2
#include<iostream> #include<string.h> #include<math.h> using namespace std; int n,m,v; int ans; int mod=1e9+7; int dp[105][105]; bool vis[105]; int main(){ cin>>n>>m>>v; int x,y; for(int i=0;i<v;i++){ cin>>x>>y; dp[x][y]=-1; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(dp[i][j]!=-1){ //该格子必须可以到达 if(i==0||j==0){ dp[i][j]=1; } else{ //因为考虑了 i=0 和 j=0 的情况，则 i-1和 j-1就不存在越界了
dp[i][j]=0; if(dp[i-1][j]!=-1){ //考虑左边一个格子是不是有障碍 无障碍则可以从该格子走 dp[i][j]+=dp[i-1][j]; } if(dp[i][j-1]!=-1){ //考虑右边一个格子是不是有障碍 无障碍则可以从该格子走 dp[i][j]+=dp[i][j-1]; } } } } } cout<<dp[n-1][m-1]; return 0; }
原文：https://www.cnblogs.com/xusi/p/12490872.html