# ADA Mini HW 3

## B07902072 資工二 陳光裕

### (1)

因為每個點能夠到達的路徑數，是其左方格子、上方格子與左上方格子的路徑數總和，因此可以利用Dynamic Programming的方式，建一個2D陣列，起始點為1，障礙物為0，從起始點往左下走，直到數到終點為止，這樣的時間複雜度為O(map_r*map_c)

### (2)

DP(Map):
    Declare a 2-D array : Table[map_r+2][map_c+2] = {};
    // start at (1,1)
    Table[1][1] = 1;
    for i in range(1,map_r+1) :
        for j in range(1,map_c+1) :
            if Map[i][j] == obstacle :
                Table[i][j] = 0;
            else :
                Table[i][j] = Table[i][j-1]+Table[i-1][j]+Table[i-1][j-1];
    
    return Table[map_r+1][map_c+1];