走格子/棋盘问题

朱雀 2021-11-19 14:46 311阅读 0赞

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

解答：我们可以把棋盘的左下角看做二维坐标的原点(0,0)，把棋盘的右上角看做二维坐标(n,n)(坐标系的单位长度为小方格的变长)

用f(i,j)表示移动到坐标f(i,j)的走法总数，其中0=<i,j<=n，我们即求f(n,n)这样我们就可以递归的定义子问题

> f(n,n)=f(n-1,n)+f(n,n-1).
> 
> 于是状态f(i,j)的状态转移方程为：
> 
> f(i,j)=f(i-1,j)+f(i,j-1)   if i,j>0
> 
> f(i,j)=f(i,j-1)            if i=0
> 
> f(i,j)=f(i-1,j)            if j=0
> 
> 初始情况就为：f(0,0)=0, f(0,1)=1, f(1,0)=1，这个问题可以在时间O(n^2)，空间O(n^2)内求解，非递归解。
> 
>   
>

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

解答：这个问题和第1题的解答是类似的。只不过最终求的是f(m,n)=f(m-1,n)+f(m,n-1)，初始为f(0,0)=0,f(0,1)=1,f(1,0)=1，所以两个解法的通用方案为：

/\*

走方格问题，给定一个m\*n的小方格子组成的棋盘，问从棋盘左下角走到右上角的走法总数。

递归解

\*/

int solve\_cube\_work(int m,int n)\{

if(m==0 && n==0)

return 0;

if(m==1 && n==0)

return 1;

if(m==0 && n==1)