圆环回原点-高频题-leetcode未收录

2021-09-25   


问题

圆环上有10个点,编号为0~9。从0点出发,每次可以逆时针和顺时针走一步,问走n步回到0点共有多少种走法

解法

1. 深度优先遍历

思路,从0点出发,n步深度优先遍历,最终是否能到0

public class Test {

    public static void main(String[] args){
        int n = 2;// 假设为2步
        int length = 10; // 圆环长度
        Solution solution = new Solution();
        solution.dfs(0, n, length);
        System.out.println(solution.count); // 结果为2
    }

    static class Solution{
        int count = 0;
        public void dfs(int index, int n, int length){
            if(n == 0){
                if(index == 0){
                    count++;
                }
                return;
            }
            dfs((index+1)%length, n-1, length);
            dfs((index-1+length)%length, n-1, length);
        }
    }
}

复杂度,dfs会执行2的n次方次 O(2^n)

2. 动态规划

套用代码随想录中的动态规划步解法

  1. 确认dp数组的定义和含义
    dp[i][j] 走i步到j的方案数
  2. 确定递推公式
    每次只能移动一步,所以只能从j-1或j+1走到
    dp[i][j] = dp[i-1][(j-1+length)%length] + dp[i-1][(j+1)%length]
  3. 如何初始化
    dp[0][0] = 1 如果不为1 最终都为0
  4. 遍历顺序
    步骤从小到大,二维数组
  5. 举例推导验证
    走2步
    第0步: 1 0 0 0 0 0 0 0 0 0
    第1步: 0 1 0 0 0 0 0 0 0 1
    第2步: 2 0 1 0 0 0 0 0 1 0

代码

public class Test {

    public static void main(String[] args){
        int n = 2;// 假设为2步
        int length = 10; //10个点
        Solution solution = new Solution();
        System.out.println(solution.getCount(n, length));
    }

    static class Solution{

        public int getCount(int n, int length){
            int[][] dp  = new int[n+1][length];
            dp[0][0] = 1;
            for(int i=1;i<=n;i++){
                for(int j=0;j<length;j++){
                    dp[i][j] = dp[i-1][(j-1+length)%length] + dp[i-1][(j+1)%length];
                }
            }
            return dp[n][0];
        }
    }
}

时间复杂度 O(n*length)

Q.E.D.