/*
標題: 振興中華小明參加了學校的趣味運動會，其中的一個項目是：跳格子。地上畫著一些格子，每個格子里寫一個字，如下所示：從我做起振我做起振興做起振興中起振興中華比賽時，先站在左上角的寫著“從”字的格子里，可以橫向或縱向跳到相鄰的格子里，但不能跳到對角的格子或其它位置。一直要跳到“華”字結束。要求跳過的路線剛好構成“從我做起振興中華”這句話。請你幫助小明算一算他一共有多少種可能的跳躍路線呢？
*/
#include <stdio.h>
#define N 5
#define M 5
int main() {int a[N][M];int i, j;for (j = 0; j < M; j++) {a[0][j] = 1;}for (i = 1; i < N; i++) {a[i][0] = 1;for (j = 1; j < M; j++) {a[i][j] = a[i-1][j] + a[i][j-1];}}printf("%d", a[N-1][M-1]);return 0;
}

? ?解決思路：?

1、“從我做起振興中華”，找茬找規律嘛，發現存在 a[i][j] = a[i-1][j] + a[i][j-1] 的遞推規則，既走當前a[i][j]格子跳躍的線路數等于 走到a[i-1][j] 跳躍線路數加上 走到a[i][j-1]格子跳躍線路數 （既，走到 “華” = 左邊“中” + 上邊“中”，走“中” = 左邊“興” +上邊“興”）。

2、橫軸第一行、縱軸第一列跳躍線路數都只有1條線路。

3、上面的代碼就是將所有格子的跳躍線路都遞推式的計算出來，然后取出最后一個格子也就是走到終點“華”的跳躍路線數打印出來。

?

---------------------?
文章轉至個人博客《學習園 》
地址：https://www.xuexiyuan.cn/article/detail/188.html