解题思路:
简单的dp问题,可以用dfs进行搜索,时间复杂度是2^n,使用记忆化搜索是n*m,dp就是简单化的记忆化搜索。
因为是只能向上和向右走,所以递推式为dp[i][j]=dp[i-1][j]+dp[i][j-1],第一行和第一列则只有一种情况,记为1,其它地方可能从左来也可能从下来,所以情况为两种相加。
参考代码:
#include <bits/stdc++.h> using namespace std; int dp[107][107]; int main () { int n,m; cin>>n>>m; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(i==1||j==1)dp[i][j]=1; else dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } cout<<dp[n][m]; return 0; }
0.0分
154 人评分
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:1721 |
C语言训练-排序问题<2> (C++代码)(sort函数)浏览:1579 |
C语言训练-谁家孩子跑最慢* (C语言代码)浏览:1508 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:770 |
求圆的面积 (C语言代码)浏览:1270 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:1057 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:1098 |
Cylinder (C语言描述+详细分析)浏览:3264 |
Tom数 (C语言代码)浏览:495 |
1071题解浏览:492 |