解题思路:
简单的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 人评分
2006年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:804 |
c primer plus 第十二章 12.1小节浏览:376 |
蛇行矩阵 (C语言代码)浏览:742 |
【排队买票】 (C语言代码)浏览:899 |
字符逆序 (C语言代码)浏览:636 |
Cylinder (C语言描述,蓝桥杯)浏览:1247 |
1126题解浏览:578 |
数组与指针的问题浏览:716 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:593 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:653 |