动态规划

#include<iostream>
using namespace std;
int i,j;
int main()
{
int m,n;
cin >> m >> n;
long long f[m][n] = {0};
f[0][0] = 1;
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
if(i == 0 && j == 0) continue;
if(i-1 < 0)
f[i][j] = f[i][j-1];
else if(j-1 < 0)
f[i][j] = f[i-1][j];
else
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
cout << f[m-1][n-1] << endl;
return 0;
}
思想: 动态规划
状态转移方程为 走到这一格的方法数=走到上面的方法数+走到左边的方法数
即 f[i][j]=f[i-1][j]+f[i][j-1]