小明参加了学校的趣味运动会, 其中的一个项目是: 跳格子.
地上画着一些格子, 每个格子里写一个字, 如下所示:(也可参见 p1.jpg)
从我做起振
我做起振兴
做起振兴中
起振兴中华
比赛时, 先站在左上角的写着 "从" 字的格子里, 可以横向或纵向跳到相邻的格子里, 但不能跳到对角的格子或其它位置.
一直要跳到 "华" 字结束. 要求跳过的路线刚好构成 "从我做起振兴中华" 这句话. 请你帮助小明算一算他一共有多少种可能的跳跃路线呢?
答案是一个整数, 请通过浏览器直接提交该数字.
注意: 不要提交解答过程, 或其它辅助说明类的内容.
答案: 35
分析:
思路一: dfs 深搜
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- // int dfs(int x,int y,int step){
- // if(step==7){
- // if(x==5&&y==4) return 1;
- // else return 0;
- // }
- // else{
- // return dfs(x+1,y,step+1)+dfs(x,y+1,step+1);
- // }
- // }
- int cnt=0;
- void dfs(int x,int y,int step){
- if(step==7){
- if(x==5&&y==4) cnt++;
- else return ;
- }
- else{
- dfs(x+1,y,step+1);
- dfs(x,y+1,step+1);
- }
- }
- int main(int argc, char const *argv[])
- {
- // cout<<dfs(1,1,0)<<endl;
- dfs(1,1,0);
- cout<<cnt<<endl;
- return 0;
- }
思路二:
dp 思想, 先说一下近似 dp 的思想的做法
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- int f(int x,int y){
- if(x==5||y==4) return 1;/* 走到边界的地方那么他就一定是一条路径, 类似 dp*/
- else{
- return f(x+1,y)+f(x,y+1);
- }
- }
- int main(int argc, char const *argv[])
- {
- cout<<f(1,1)<<endl;
- return 0;
- }
下面是正宗 dp 做法:
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- using namespace std;
- int main(){
- int dp[6][5];
- memset(dp,0,sizeof(dp));
- dp[1][1]=1;
- for( int x=1; x<=5; x++ ){
- for( int y=1; y<=4; y++ ){
- /*[x][y]位置要么从 [x-1][y] 向右走, 要么从 [x][y-1] 向下走 */
- dp[x][y]+=dp[x-1][y]+dp[x][y-1];
- // printf("dp[%d][%d]=%d\n",x,y,dp[x][y]);
- }
- }
- cout<<dp[5][4]<<endl;
- return 0;
- }
振兴中华(dfs or dp )
来源: http://www.bubuko.com/infodetail-2970377.html