# 网格路径问题

2013-09-07

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

def r(x, y):

if x == 0 and y == 0:
p = 0
elif x == 0 or y == 0:
p = 1
else:
p = r(x - 1, y) + r(x, y - 1)

return p


def r(x, y):
d = []
for i in range(y + 1):
t = [0] * (x + 1)
d.append(t)

for iy in range(y + 1):
for ix in range(x + 1):
if ix == 0 and iy == 0:
v = 0
elif ix == 0 or iy == 0:
v = 1
else:
v = d[iy - 1][ix] + d[iy][ix - 1]
d[iy][ix] = v

return d[y][x]


### 评论：

MatheMatrix

oldj

wenlong

oldj

wenlong

//C++.动态创建二维数组真不方便
#include
using namespace std;
unsigned long long r1 (size_t x, size_t y)
{
unsigned long long p;
if (x == 0 && y == 0)
p = 0;
else if (x == 0 || y == 0)
p = 1;
else
p = r1(x - 1, y) + r1(x, y - 1);

return p;


}

unsigned long long r2 (const size_t x, const size_t y)
{
unsigned long long* p = new unsigned long long[(x+1)(y+1)];
for (size_t i = 0; i <= x; ++i)
p[i
(y+1)+0] = 1;
for (size_t i = 0; i <= y; ++i)
p[0*(y+1)+i] = 1;
for (size_t ix = 1; ix <= x; ++ix)
for (size_t iy = 1; iy <= y; ++iy){
p[ix*(y+1)+iy] = p[(ix-1)(y+1)+iy] + p[ix(y+1)+(iy-1)];
}
size_t line = 0;
for (size_t a = 0; a < (x+1)(y+1); ++ a){
cout << p[a] << "t";
if (!(++line % (y+1)))
cout << endl;
}
unsigned long long ret = p[x
(y+1)+y];
delete p;
return ret;
}
int main(int argc, char const *argv[])
{
cout << r2(30,30);
return 0;
}

oldj

oldj

Leo

oldj

Leo