您好,登錄后才能下訂單哦!
題目一看;
感覺可以用回溯法 就是從(0.0)開始 走到下一步 再走下一步 走到盡頭了 向右邊走 到盡頭了回去上一個格子 再從上一個格子換一個方向 走 因為只能走2個方向 如果一個格子2個方向都走完了 就又回到上一個
通過這樣的辦法 可以列出所有路徑 并且找到所有的路徑數(shù)之和。
回溯法遞歸實現(xiàn):
代碼如下:
//遞歸版
void uniquePaths2(int m, int n,int H,int L,int *res)
{
if (m == H && n == L)
{
(*res)++;
return 0;
}
if(m<=H-1)
uniquePaths2(m + 1, n,H,L,res);
if(n<=L-1)
uniquePaths2(m , n+1,H,L,res);
}
int uniquePaths(int m, int n) {
int res = 0;
uniquePaths2(1, 1,m,n,&res);
return res;
}
int main()
{
int m = 4, n = 4;
printf("%d\n", uniquePaths(m, n));
return 0;
}
程序跑出來沒問題 用題目提供的樣本數(shù)據(jù) 測試都ok
但是再大一點到 m=20 n=15的時候就超時了 隨著m n的增加時間幾乎也以幾何級的速度增長。程序運行幾秒cpu就罵人了。。。
然后我想試試迭代版的時間如何
回溯法迭代版:
//迭代版
struct Point
{
int x, y;
};
int uniquePaths3(int m,int n)
{
int x = 0, y = 0,lsx=0,lsy=0;
int zt[100][100] = { 0 };
int sum = 0;
struct Point Yl[100][100] = { 0 };
while (1)
{
if (x >= m || y >= n)//該點超出范圍了 返回
{
lsx = Yl[x][y].x;
lsy= Yl[x][y].y;
x = lsx; //返回上一點
y = lsy;
continue;
}
switch (zt[x][y])
{
case 0://該點未使用過 默認向下
zt[x][y]++; //表明已經(jīng)向下走了一次
x += 1;
Yl[x][y].x = x-1;
Yl[x][y].y= y;
break;
case 1:
zt[x][y]++; //表明已經(jīng)向下走了一次
y += 1;
Yl[x][y].x = x ;
Yl[x][y].y = y-1;
break;
case 2: //該點下右都走完了 返回上一點
if (x == 0 && y == 0)
{
return sum;
}
zt[x][y] = 0;
lsx = Yl[x][y].x;
lsy = Yl[x][y].y;
x = lsx; //返回上一點
y = lsy;
break;
default:
break;
}
if (x == m - 1 && y == n - 1 && zt[x][y] == 0)
sum++;
}
return sum;
}
int main()
{
int m = 20, n = 15;
printf("%d\n", uniquePaths3(m, n));
//printf("%d\n", uniquePaths(m, n));
return 0;
}
結(jié)果效果跟遞歸版一樣
。。。然后我就想應(yīng)該是從0,0 到終點的話會出現(xiàn)很多重復(fù)的工作,比如m=10 n=10 從中間5,5到 9,9 點如果有N種走法 那么剛開始 0,0 開始遍歷到 5,5的時候 和 1,1遍歷到5,5的時候都會從5,5遍歷到9,9了。這就重復(fù)工作了??梢钥紤]把5,5到9,9的走法記錄下來,然后到5,5的時候就讀取這個記錄就行了。
但是不能從0,0開始
應(yīng)該從9,9終點開始向左邊走。
然后走到左邊終點的時候
就返回到上一層的末尾
如此反復(fù)到0,0 這樣的話在遍歷的過程中每個點都可以獲取向下和向右的走法數(shù)量 兩者之和即為該點到終點的走法數(shù);
代碼如下:
#include <stdio.h>
/*
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
*/
int uniquePaths2(int m, int n,int h,int l,int **HashMap)
{
int Sum = 0;
if (m<0||n<0)//坐標非法
return 0;
if (n >= 0 && n <= l-1)//如果還不用切換到上一行
{
if (n >= 0 && n < l-1)//可以向右讀
{
Sum += HashMap[m][n + 1];
}
if (m >= 0 && m < h-1) //可以向下讀
{
Sum += HashMap[m+1][n];
}
if (h-1 == m && l-1 == n) Sum = 1;
HashMap[m][n] = Sum;
//切換到上一行
if (0 == m && n == 0)
{
return HashMap[0][0];
}
if (n == 0)
{
return uniquePaths2(m - 1, l-1,h,l,HashMap);//返回到上一行
}
else
return uniquePaths2(m, n - 1,h,l,HashMap);
}
return 0;
}
int uniquePaths(int m, int n)
{
int xhbl = 0, xhbl2 = 0;
//int HashMap[100][100] = { 0 };//記錄 leetcode中不能用全局變量 所以只能這樣
int **HashMap = malloc(sizeof(int*) * 100);
for(xhbl=0;xhbl<100;xhbl++)
HashMap[xhbl]=malloc(sizeof(int) * 100);
for (xhbl = 0; xhbl < 100; xhbl++)
{
for (xhbl2 = 0; xhbl2 < 100; xhbl2++)
{
HashMap[xhbl][xhbl2] = 0;
}
}
HashMap[m-1][n-1] = 1;
return uniquePaths2(m - 1, n - 1, m, n,HashMap);
}
int main()
{
printf("%d", uniquePaths(7, 3));
return 0;
}
提交到leetcode:
沒毛病,就是時間太慢了。。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。