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

本文主要是介绍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.图解