C/C++ Coding Exercise – Unique Paths – LeetCode Online Judge – Dynamic Programming – Recursive Formula

Remember a couple days ago, I write a solution to this puzzle using Dynamic Programming (DP)? The DP solution helps to avoid duplicate computation in the sub-problems (smaller size). That puzzle asks to you find a minimal path from top-left to bottom right while the walking direction can be right or down each step. Along checking the sum each step, using DP will compute the sub-solution for the sub problem which can be combined into a bigger problem. Now, this puzzle (the original page on leet code online judge is here, so you can submit your solution first) is similar, let’s have a look:

It is the same problem input, a grid of size m * n the difference is that it asks you the distinct ways to walk from the top-left to the bottom right. At each square, we can come from two possible positions, the one on its top and the one on its left. Of course, the first row and column can only come from one possible position, which has the answer of one (because it is not possible to come from left and top any more, respectively).

Base on this observation, we can have the following equations:

and and .

Of course, you can write a recursion function, but it will be slow and possibly causing stack overflow given such input range (at most 100). Therefore, using a two dimensional array (static array should be fine because the largest input is 100) is more than enough.

The C/C++ solution is easy to cook up and I didn’t even debug the solution, I just simply write this code (error-free) in the browser textarea, and submit it. It gets accepted even for the first time. The space complexity is O(m*n) and the running time complexity is O(m*n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int uniquePaths(int m, int n) {
        int sol[100][100];
        for (int i = 0; i < n; i ++) {
            sol[0][i] = 1;
        }
        for (int i = 0; i < m; i ++) {
            sol[i][0] = 1;
        }
        for (int i = 1; i < m; i ++) {
            for (int j = 1; j < n; j ++) {
                sol[i][j] = sol[i - 1][j] + sol[i][j - 1];
            }
        }
        return sol[m - 1][n - 1];
    }
};

class Solution {
public:
    int uniquePaths(int m, int n) {
        int sol[100][100];
        for (int i = 0; i < n; i ++) {
            sol[0][i] = 1;
        }
        for (int i = 0; i < m; i ++) {
            sol[i][0] = 1;
        }
        for (int i = 1; i < m; i ++) {
            for (int j = 1; j < n; j ++) {
                sol[i][j] = sol[i - 1][j] + sol[i][j - 1];
            }
        }
        return sol[m - 1][n - 1];
    }
};

Any one can think of a pure formula for this using combinatoric mathematics knowledge?
–EOF (The Ultimate Computing & Technology Blog) —