Ring back to origin problem - byte jumping high frequency problem

One 、 Title Description

There are... On the ring 10 A little bit , The number is 0~9. from 0 Leaves at , You can take one step counterclockwise and clockwise at a time , Ask to leave n Step back 0 How many ways are there to go .

Example 1：

 Input : 2
 Output : 2
 explain ： Yes 2 Kind of plan . Namely 0->1->0 and 0->9->0

Two 、 Problem solving

Dynamic programming

This question is similar to climbing stairs , Use dynamic programming ： go n Step to 0 Number of alternatives = go n-1 Step to 1 Number of alternatives + go n-1 Step to 9 Number of alternatives .

dp[i][j] From 0 Let's go at six i Step to j The number of schemes .
State transition equation ：

• go i Step by step j There are n Medium method be equal to { go i-1 Step to j-1} + { go i-1 Step to j+1}, Because there is a loop , So you need to go to j-1 It could be negative
• dp[i][j] = dp[i-1][(j-1+length)%length] + dp[i-1][(j+1+length)%length];

class Solution {
    
    public int backToOrigin(int k) {
    
        int[][] dp = new int[k + 1][10];
        dp[0][0] = 1;
        for (int i = 1; i <= k ; i++) {
    
            for (int j = 0; j < 10; j++) {
    
                dp[i][j] = dp[i - 1][(j - 1 + 10) % 10] + dp[i - 1][(j + 1) % 10];
            }
        }
        return dp[k][0];
    }
}

extend

class Solution {
    
    public int backToOrigin(int n, int k) {
    
        if (n == 0) {
    
            return 1;
        }
        if (n == 2) {
    
            if (k % 2 == 0) {
    
                return k;
            } else {
    
                return 0;
            }
        }
        int[][] dp = new int[k + 1][n];
        dp[0][0] = 1;
        for (int i = 1; i < k + 1; i++) {
    
            for (int j = 0; j < n; j++) {
    
                dp[i][j] = dp[i - 1][(j - 1 + n) % n] + dp[i - 1][(j + 1) % n];
            }
        }
        return dp[k][0];
    }
}