1576. [算法课动态规划]走网格

include

using namespace std; int f[100][100];

/* 设f[m][n],f[i][j]表示走到第i行第j列的走法有多少种; 最终结构是f[m-1][n-1];而最后一步可能是从它的上方[m-2][n-1] 或者左方[m-1][n-2]走来的,故f[m-1][n-1]=f[m-2][n-1]+f[m-1][n-2]; 这就完成了对问题的划分,即化成一个个子问题,现在继续算f[m-2][n-1],和f[m-1][n-2],然后继续。

*/ int main(){

int n,m; cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(i==0||j==0){ f[i][j]=1; } else f[i][j]=f[i-1][j]+f[i][j-1]; } } cout<<f[n-1][m-1]<<endl;

}