從經典問題學遞歸：3X4的方格從左上角A走到右下角B 只能向右向下走一共有多少種走法？

lvzishen 發布于2019-08-23 17:56 / 3605人閱讀

摘要：題目的方格從左上角走到右下角只能向右向下走一共有多少種走法圖形題目轉化為圖形之后就是，從方格走到方格有多少種方案每次走一格分析根據題目我們知道只能往右走或者向下走，那么從，格子走到，格子只有一種方案，從，格子走到，格子也只有一種方案。

題目：3X4的方格 從左上角A走到右下角B 只能向右向下走 一共有多少種走法？

圖形：題目轉化為圖形之后就是，從(1, 1)方格走到(3, 4)方格有多少種方案（每次走一格）？

分析：
1、根據題目我們知道只能往右走或者向下走，那么從(2， 4)格子走到(3， 4)格子只有一種方案，從(3， 3)格子走到(3， 4)格子也只有一種方案。
2、以此類推，到某個格子A的走法 = A上面的格子走法 + A左邊的格子走法；
3、如果碰到第一行或者第一列的格子，那么走法只有一種
4、如果碰到第一個格子，我們認為不需要走，即走法為0

總結：
1、這種把一個復雜的問題分解成若干個有相同規律的子問題的方法，我們稱之為遞歸。
2、遞歸由遞歸條件和遞歸出口組成，其中遞歸出口非常重要。
3、分析中的第2點我們稱之為遞歸條件。
4、分析中的點3、4點我們稱之為遞歸出口（返回明確的值）。

代碼：

// N X M的方格 從左上角A(1, 1)走到右下角B(N, M) 只能向右向下走 一共有多少種走法？
function calc(x, y){
    // 坐標(1, 1)  遞歸出口
    if(x == 1 && y == 1) return 0;

    // 坐標(x, 1) (1, y) 遞歸出口
    if(x == 1 || y == 1) return 1;
    
    // 遞歸條件
    if(x > 1 && y > 1) {
        return calc(x-1, y) + calc(x, y-1);
    }
       
    // 不符合條件，直接返回0
    return 0;
}

calc(3, 4); // 10

問題：
根據上面的分析，我們知道在遞歸的過程中，會有很多重復的格子，非常浪費性能，當計算的數字越大，遞歸的性能也會越低，怎么提高遞歸的性能呢？下次我們再介紹（剪枝）。

GPU云服務器云服務器阿里云的服務器從公賬怎么走編程語言共有多少種 js圖片從左向右移動從服務器只能讀嗎

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/104372.html

動態規劃入門（以爬樓梯為例）

摘要：動態規劃算法通常基于一個遞推公式及一個或多個初始狀態。動態規劃有三個核心元素最優子結構邊界狀態轉移方程我們來看一到題目題目有一座高度是級臺階的樓梯，從下往上走，每跨一步只能向上級或者級臺階。概念動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。動態規劃算法通常基于一個遞推公式及一個或多個初始狀態...

cyixlq 2019-08-23 10:52 評論0 收藏0
前端跳槽面試算法——動態規劃

摘要：我記得大三參加騰訊的校招面試時只準備了幾種常見的排序算法就足以應對了，然而今年包括今日頭條在內的多家大廠的前端筆試題目中都出現了貪心算法動態規劃分治算法等進階性的算法題目。本篇博客參考今日頭條銀國徽老師的《js版數據結構與算法》Part1改編自《漫畫算法》原作者：程序員小灰前言眾所周知，與后臺開發人員相比，算法是我們前端開發人員的一個弱項。而近兩年隨著互聯網行業競爭愈發激烈，市場上對前端崗位...

mushang 2019-05-21 19:07 評論0 收藏0
有關排列組合的一道算法題

摘要：有關排列組合的一道算法題一題目內容廢話不多說，先上題目有一個的網格，左下角為，右上角為，規定每次只能走一步，并且方向只能是向上或者向右，求到共有多少種走法例如一個日字形的格子就是一個的網格，共有種走法并用寫出程序算法。有關排列組合的一道算法題一、題目內容廢話不多說，先上題目：有一個 n × m 的網格，左下角為A，右上角為B，規定每次只能走一步，并且方向只能是向上或者向右，求A...

ephererid 2019-08-20 18:18 評論0 收藏0
備戰藍橋杯——算法訓練之過河馬

摘要：而眾所周知，馬是要走日子格的。輸出格式輸出有一行，一個數表示走法數。那為了防止爆掉，我們每加完一條路的總步數之后就取一遍余。題目解法思路如上述，但是這里有一個我之前從來沒有注意過的問題，導致我一直只有分。三題解四題目鏈接過河馬 ...

xorpay 2021-11-15 11:38 評論0 收藏0
每日一道算法題 - KaprekarsConstant(hard-2)

摘要：更多的小算法練習，可以查看我的文章。規則使用語言，使用函數讀取，它將是一個字符串，指的是棋盤上點的位置。使用遞歸函數去解決，需要清楚判斷的臨界點，比如和時，只有一種選擇。雖然都是很簡單的算法，每個都只需5分鐘左右，但寫起來總會遇到不同的小問題，希望大家能跟我一起每天進步一點點。更多的小算法練習，可以查看我的文章。規則 Using the JavaScript language, h...

OnlyLing 2019-08-22 18:41 評論0 收藏0