蓝桥杯13-20届真题答案和解析（Java 大学 B 组）2013年省赛真题3

一、振兴中华[填空]

1.题目描述2.简要分析3.代码实现（递归）4.答案

小明参加了学校的趣味运动会，其中的一个项目是：跳格子。
地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）

从我做起振
我做起振兴
做起振兴中
起振兴中华

比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的>格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。

要求跳过的路线刚好构成“从我做起振兴中华”这句话。

请你帮助小明算一算他一共有多少种可能的跳跃路线呢？

答案是一个整数，请通过浏览器直接提交该数字。 注意：不要提交解答过>程，或其它辅助说明类的内容。

读题，大致意思是：从左上角到右下角走方格，路线恰好是从我做起振兴中华的可能种数。
这种走二维方格的，给人第一感觉就是DFS，试错然后回溯。但用在这里，未免小题大做了。如果使用DFS，需要先构造矩阵，然后DFS，然后路线判断。还是有些许的麻烦的。
观察这个矩阵，可以发现一个特点：除边界和第一个字外，其余的字，都是恰好可以接在它的左边或者上面后面的。那么也就是说，可以从上到下开始逐项的累加。其实也就是动态规划。
不难发现，如果使用f(i,j)表示走到第i行，第j列已有的种数，那么状态转移方程是:f(i,j)=f(i + 1, j) + f(i, j + 1)。
如果使用递归的方式来实现这个dp，那么终止条件就是i==3,有f(3,j)=1 ，或者j==4,有f(i,4)=1。

public class _03_振兴中华_DFS {
	  public static void main(String[] args) {
		  //重复、变化、边界
	    int ans = f(0, 0);
	    System.out.println(ans);
	  }

	  private static int f(int i, int j) {
	    if (i == 3 || j == 4) return 1;
	    return f(i + 1, j) + f(i, j + 1);//将两种走法的路线数相加
	  }
	}

35