解题思路:
简单的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语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:736 |
C语言程序设计教程(第三版)课后习题8.2 (Java代码)浏览:2269 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:684 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:562 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:467 |
模拟计算器 (C++代码)浏览:806 |
第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略浏览:1145 |
简单的事情 (C语言代码)浏览:635 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:549 |
数列排序 (C语言代码)浏览:608 |