从经典问题学递归：3X4的方格从左上角A走到右下角B 只能向右向下走一共有多少种走法？

lvzishen 发布于2019-08-23 17:56 / 3341人阅读

摘要：题目的方格从左上角走到右下角只能向右向下走一共有多少种走法图形题目转化为图形之后就是，从方格走到方格有多少种方案每次走一格分析根据题目我们知道只能往右走或者向下走，那么从，格子走到，格子只有一种方案，从，格子走到，格子也只有一种方案。

题目：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图片从左向右移动从服务器只能读吗

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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