方格到右下角的方格,共有多少条路径(只允许向右和向下)"/>
经典问题:对于一个m*n的网格,从左上角的方格到右下角的方格,共有多少条路径(只允许向右和向下)
两种方法:
1、递归
int sum(int m, int n)//递归
{if (m == 1 || n == 1)return 1;int total = sum(m - 1, n) + sum(m, n - 1);return total;
}
2.非递归
int sum(int m, int n)//非递归
{int ** a = (int**)calloc(m, sizeof(int*));for (int i = 0; i < m; i++){a[i] = (int*)calloc(n, sizeof(int));}for (int i = 0; i < m; i++){a[i][0] = 1;//第一列赋值为1a[0][i] = 1;}//int t;for (int i = 1; i < m; i++){for (int j = 1; j < n; j++){a[i][j] = a[i - 1][j] + a[i][j - 1];// t = a[i][j];//int c=t;}}return a[m-1][n-1];
}
更多推荐
经典问题:对于一个m*n的网格,从左上角的方格到右下角的方格,共有多少条路径(只允许向右和向下)
发布评论