Brute force recursion to dynamic programming 01

Topic 1

Suppose there are N positions in a row, denoted as 1~N, and N must be greater than or equal to 2.
The robot is at the M position in the row at the beginning(M must be one of 1~N).
If the robot comes to position 1, then the next step can only go to position 2 to the right.
If the robot comes to the N position, then the next step can only go to position N-1 to the left.
If the robot comes to the middle position, then then next step can go left or right.
How many ways are there to specify that the robot must take K steps and finnaly reach the P position(P is also one of 1~N).
Given four parameters N, M, K, P, returns the number of methods.

Solution #1 Brute force recursion

1. Base case: Only when K is zero and the current position of robot is the P position find one way.

2. Boundary conditions: When robot current position is 1. The next step can only go to the right. When robot current position is N. The next step can only go to the left.

3. Middle position: When robot in the any middle position. The next step can go left or right.
   

public static int myWays1(int N, int M, int P, int K) {
        return myProcess1(M, K, P, N);
    }
// cur: robot current position
// rest: remaining steps
// aim: target position
// N: position of 1~N
    public static int myProcess1(int cur, int rest, int aim, int N) {
        if (rest == 0) { // no steps 
            return cur == aim ? 1 : 0;
        }
        if (cur == 1) { // current position is 1,go to right
            return myProcess1(cur + 1, rest - 1, aim, N);
        }
        if (cur == N) { // current position is N, go to left 
            return myProcess1(N - 1, rest - 1, aim, N);
        }
        // current position in any middle position, go to left or right
        return myProcess1(cur + 1, rest - 1, aim, N) + myProcess1(cur - 1, rest - 1, aim, N);
    }

Solution #2 Memoized search

In Solution #1, can be found that only cur and rest parameters are changing. It can be seen from the figure that there is a process of repeated calculation in Solution #1. So we can use a cache to put already calculation values.

public static int myWays2(int N, int start, int aim, int K) {
        // dp cache
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        return myProcess2(start, K, aim, N, dp);
    }

    public static int myProcess2(int cur, int rest, int aim, int N, int[][] dp) {

        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        int ans = 0;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
            ans = myProcess2(cur + 1, rest - 1, aim, N, dp);
        } else if (cur == N) {
            ans = myProcess2(N - 1, rest - 1, aim, N, dp);
        } else {
            ans = myProcess2(cur + 1, rest - 1, aim, N, dp) + myProcess2(cur - 1, rest - 1, aim, N, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }

Solution #3 Dynamic programming

1. Prepare an N+1 * K+1 two-dimensional array. Rows indicate position, columns indicate remaining steps.

2. Find base case, when remaining steps is zero and the position is P, so set dp[P][0] = 1.

3. The first row depends on the [rest - 1] position of the next row.
   The last row depends on the [rest - 1] position of previous row.
   The middle row depends on the sum of [rest - 1] postition of previous and next row.

4. Return the result is dp[M][K].
   

    public static int myWays3(int N, int M, int P, int K) {
        int[][] dp = new int[N + 1][K + 1];
        dp[P][0] = 1;

        for (int rest = 1; rest <= K; rest++) {
            dp[1][rest] = dp[2][rest - 1];
            for (int cur = 2; cur < N; cur++) {
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];
        }

        return dp[M][K];
    }