2.算法:棋盘路径问题。走格子/棋盘问题 有多少条路径可走

2024-04-28 05:32

本文主要是介绍2.算法:棋盘路径问题。走格子/棋盘问题 有多少条路径可走,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.问题描述

给定一个m*n的格子或棋盘,问从左上角走到右下角的走法总数(每次只能向右或向下移动一个方格边长的距离。


2.基本要求

期盼路径算法,走方格问题,给定一个m*n的小方格子组成的棋盘,问从棋盘左上角走到右下角的走法总数。
要求:只能向右走或者向下走。求出从左上到右下的路径数。


如图一所示,是一个棋盘,要求从start开始到end结束的路径数。


图一
3.算法思想:递归
不过最终求的是f(m,n)=f(m-1,n)+f(m,n-1),初始为f(0,0)=0,f(0,1)=1,f(1,0)=1


4.主要代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
int cube(int m,int n)
{if (m > 1 && n > 1){return cube(m, n - 1) + cube(m - 1, n);}else if ((m == 0) && (n>1)){return cube(m,n-1);}else if ((n == 0) && (m>1)){return cube(m-1,n);}else if ((m == 0 && n == 1) || (m == 1 && n == 0)){return 1;}else return 0;
}
int main()
{printf("%d",cube(9,8));system("PAUSE");
}

5.时间复杂度分析

我们可以把棋盘的左下角看做二维坐标的原点(0,0),把棋盘的右上角看做二维坐标(n,n)(坐标系的单位长度为小方格的变长)
用f(i,j)表示移动到坐标f(i,j)的走法总数,其中0<=i,j<=N, f(m,n)=f(m-1,n)+f(m,n-1),初始情况就为:f(0,0)=0, f(0,1)=1, f(1,0)=1,这个问题可以在时间O(n^2),空间O(n^2)内求解。


6.图解

如图所示,为空间复杂度分析。

这里写图片描述

这篇关于2.算法:棋盘路径问题。走格子/棋盘问题 有多少条路径可走的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/942424

相关文章

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Spring MVC跨域问题及解决

《SpringMVC跨域问题及解决》:本文主要介绍SpringMVC跨域问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录跨域问题不同的域同源策略解决方法1.CORS2.jsONP3.局部解决方案4.全局解决方法总结跨域问题不同的域协议、域名、端口

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

基于.NET编写工具类解决JSON乱码问题

《基于.NET编写工具类解决JSON乱码问题》在开发过程中,我们经常会遇到JSON数据处理的问题,尤其是在数据传输和解析过程中,很容易出现编码错误导致的乱码问题,下面我们就来编写一个.NET工具类来解... 目录问题背景核心原理工具类实现使用示例总结在开发过程中,我们经常会遇到jsON数据处理的问题,尤其是