Violence recursion to dynamic programming 01 (robot movement)

1. subject

2. Recurrence of violence

    /** * @param length  Total length  * @param cur  The current position  * @param steps  Remaining steps  * @param target  Target location  * @return */
    public static int getWays(int length, int cur, int steps, int target) {
    
        // If the remaining steps are 0
        if (steps == 0) {
    
            // Judge whether the current position is the target position 
            if (cur == target) {
    
                return 1;
            } else {
    
                return 0;
            }
        }
        // Left boundary 
        if (cur == 1) {
    
            // Move to 2 Location 
            return getWays(length, 2, steps - 1, target);
        }
        // Right border 
        if (cur == length) {
    
            // Move to the penultimate position on the right 
            return getWays(length, length - 1, steps - 1, target);
        }
        // In the middle 
        return getWays(length, cur - 1, steps - 1, target) + getWays(length, cur + 1, steps - 1, target);
    }

Dynamic programming

   /** * @param length  Total length  * @param cur  The current position  * @param steps  Remaining steps  * @param target  Target location  * @return */
    public static int getWays2(int length, int cur, int steps, int target) {
    
        // Longitudinal   by   route , Horizontal row is the number of remaining steps 
        int[][] dp = new int[length + 1][steps + 1];
        // The first 1 Column initialization , When the number of steps is 0 When , If 
        dp[target][0] = 1;
        for (int i = 1; i <= steps; i++) {
    
            // The first 0 Behavior length=0, non-existent 
            // The first line can be initialized directly , Because it is located on the left boundary , You can only move to the second position 
            dp[1][i] = dp[2][i - 1];
            for (int j = 2; j < length; j++) {
    
                // Except for one line and the last line （ Left and right ）, The rest of the lines are the sum of left and right 
                dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
            }
            // If you encounter the right boundary , Go straight to the penultimate 
            dp[length][i] = dp[length - 1][i - 1];
        }
        // Return the number of target locations 
        return dp[cur][steps];
    }

    public static void main(String[] args) {
    
        System.out.println(getWays(4, 2, 4, 4));
        System.out.println(getWays(5, 2, 6, 4));
        System.out.println(getWays2(4, 2, 4, 4));
        System.out.println(getWays2(5, 2, 6, 4));
    }