【排列组合】给定一个M*N的格子或棋盘,从左下角走到右上角的走法总数(每次只能向右或向上移动一个方格边长的距离)

版权声明:本文为CSDN博主「梵解君」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。网址:yii666.com<

原文链接:https://blog.csdn.net/hadeso/article/details/12622743

--------------------------------------------------------------------------------------------------------------------

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

f(i, j)表示移动到坐标f(i, j)的走法总数,其中0=<i, j<=n,设f(m, n)代表从坐标(0,0)到坐标(m,n)的移动方法,

f(m, n) = f(m-1, n) + f(m, n-1).文章来源地址https://www.yii666.com/article/754005.html

于是状态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(i, j)的状态转移方程为:

【排列组合】给定一个M*N的格子或棋盘,从左下角走到右上角的走法总数(每次只能向右或向上移动一个方格边长的距离)文章来源地址:https://www.yii666.com/article/754005.html

递归结束条件为:f(0,0)=0, f(0,1)=1, f(1,0)=1。这个问题可以在时间O(n^2),空间O(n^2)内求解。

递归解法文章地址https://www.yii666.com/article/754005.html

//递归解法
int process(int m, int n) {
//永远不可能达到m & n同时为0的条件,除非输入m=n=0
if (m == 0 && n == 0)
return 0;
if (m == 0 || n == 0)
return 1;
return process(m, n - 1) + process(m - 1, n);
}

非递归解法网址:yii666.com

int processNew(int m,int n){
int **Q=new int*[m+1];
for(int i=0; i<=m; ++i){
Q[i]=new int[n+1]();
}
//初始化
Q[0][0]=0;
for(int j=1; j<=n; ++j)
Q[0][j]=1;
for(int i=1; i<=m; ++i)
Q[i][0]=1;
//迭代计算
for(int i=1; i<=m; ++i){
for(int j=1; j<=n; ++j){
Q[i][j]=Q[i-1][j]+Q[i][j-1];
}
}
int res=Q[m][n];
delete [] Q;
return res;
}

  

解法2:这个题目其实是一个组合问题。对方向编号,向上是0,向右是1,那么从左下角走到右上角一定要经过M 个1和N个0。这个题目可以转化为从M+N个不同的盒子中挑出M个盒子有多少种方法。答案是C(M+N, M),或者C(M+N, N)的组合数

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png