坐标系从(0,0)点走到(9,9)点,只能向右或者向上走,其中有些点不能走,问有多少种走法?
如图:假如。的位置不能走。(希望图能分辨清,左下角是(0,0))
..........
..........
..........
..。。......
....。.....
..........
..........
..........
..........
..........
笔算的方法:
设左下为S(0,0), 右上为T(9,9);
三个障碍点分别为 A(2,6) B(3,6) C(4,5)
那么答案就是 (S到T的路径总数)- (经过A or B or C的路径总数);
S到T的路径总数 = C(18,9) = 18!/9!/9! = 48620
后者可以用 (S->A)*(A->T) + (S->B)*(B->T) - (S->A)*(A->B)*(B->T) +
(S->C)*(C->T)计算。
即C(18,9) - [C(8,2)*C(10,3) + C(9,3)*(9,3) - C(8,2)*1*C(9,3) +
C(9,4)*C(9,4)] = 48620 - [3360 + 7056 - 2352 + 15876] = 48620 - 23940 = 24680
---------------------------
DP的方程就是:
F[0][k] = 1,F[k][0] = 1;
而对于i,j > 0,有
{ F[i-1][j] + F[i][j-1], 若(i,j)不是障碍点;
F[i][j] = {
{ 0 , 否则;
那么F[9][9]就是答案
先这样
1 . . . . . . . . .
1 . . . . . . . . .
1 . . . . . . . . .
1 . 0 0 . . . . . .
1 . . . 0 . . . . .
1 . . . . . . . . .
1 . . . . . . . . .
1 . . . . . . . . .
1 . . . . . . . . .
0 1 1 1 1 1 1 1 1 1
然后对所有未置值的点,计算
a(i,j) = a(i-1,j) + a(i,j-1)
算到a(9,9)就行了
1 10 27 52 85 252 1015 3502 1000224680
1 9 17 25 33 167 763 2487 6500 14678
1 8 8 8 8 134 596 1724 4013 8178
1 7 0 0 0 126 462 1128 2289 4165
1 6 21 56 0 126 336 666 1161 1876
1 5 15 35 70 126 210 330 495 715
1 4 10 20 35 56 84 120 165 220
1 3 6 10 15 21 28 36 45 55
1 2 3 4 5 6 7 8 9 10
0 1 1 1 1 1 1 1 1 1
最后结果是有24680种走法