intro-dp-exmp2-td.cpp

char A[MAX_N][MAX_M]; // assume the board's data is in A[1.n][1..m]
int dp[MAX_N][MAX_M]; // initially set all to -1 to mark as "not done yet"

int count_paths(int i, int j) {
    if (i < 1 || j < 1)
        return 0;
    if (A[i][j] == '#')
        return 0;
    if (i == 1 && j == 1)
        return 1;
    
    if (dp[i][j] != -1) // if already done this case
        return dp[i][j];
    // otherwise, calculate and remember then return
    dp[i][j] = count_paths(i-1, j) + count_paths(i, j-1);
    return dp[i][j];
}

// according to the above example:
// cout << count_paths(5, 4) << endl;
// result = 3