一、振兴中华[填空]
1.题目描述2.简要分析3.代码实现(递归)4.答案
一、振兴中华[填空] 1.题目描述2.简要分析小明参加了学校的趣味运动会,其中的一个项目是:跳格子。
地上画着一些格子,每个格子里写一个字,如下所示:(也可参见p1.jpg)从我做起振
我做起振兴
做起振兴中
起振兴中华比赛时,先站在左上角的写着“从”字的格子里,可以横向或纵向跳到相邻的>格子里,但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。
要求跳过的路线刚好构成“从我做起振兴中华”这句话。
请你帮助小明算一算他一共有多少种可能的跳跃路线呢?
答案是一个整数,请通过浏览器直接提交该数字。 注意:不要提交解答过>程,或其它辅助说明类的内容。
3.代码实现(递归)读题,大致意思是:从左上角到右下角走方格,路线恰好是从我做起振兴中华的可能种数。
这种走二维方格的,给人第一感觉就是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);//将两种走法的路线数相加 } }4.答案
35
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)