LeetCode 补充题 2. 圆环回原点问题

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：滚动数组优化
相似题目

题目描述

✅ 补充题 2. 圆环回原点问题

思路分析

解法一：动态规划（推荐）

核心思路：

定义 dp[i][j] 表示走 i 步后恰好在位置 j 的方案数（圆环共 n 个位置，编号 0 到 n-1）。

初始状态：dp[0][0] = 1，出发点在 0，走 0 步方案数为 1。

状态转移：每走一步可以向左或向右移动，位置对 n 取模：

dp[i][j] += dp[i-1][(j-1+n) % n]（从左边来）

dp[i][j] += dp[i-1][(j+1) % n]（从右边来）

最终答案：dp[n][0]，即走 n 步后回到原点 0 的方案数。

关键点：使用 (j ± 1 + n) % n 处理圆环边界，避免越界。

复杂度分析：

时间复杂度：O(n²)，其中 n 为圆环大小，共 n 步，每步遍历 n 个位置

空间复杂度：O(n²)，其中 n 为圆环大小，dp 数组大小为 (n+1) × n

class Solution {
    public int backToOrigin(int n) {
        // dp[i][j] 表示走 i 步后处于位置 j 的方案数
        int[][] dp = new int[n + 1][n];
        // 初始状态：走 0 步，在位置 0
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < n; j++) {
                // 从左边位置 (j-1+n)%n 走一步到达 j
                dp[i][j] += dp[i - 1][(j - 1 + n) % n];
                // 从右边位置 (j+1)%n 走一步到达 j
                dp[i][j] += dp[i - 1][(j + 1) % n];
            }
        }

        // 走 n 步后回到原点 0 的方案数
        return dp[n][0];
    }
}

func backToOrigin(n int) int {
    // dp[i][j] 表示走 i 步后处于位置 j 的方案数
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    // 初始状态：走 0 步，在位置 0
    dp[0][0] = 1

    for i := 1; i <= n; i++ {
        for j := 0; j < n; j++ {
            // 从左边位置 (j-1+n)%n 走一步到达 j
            dp[i][j] += dp[i-1][(j-1+n)%n]
            // 从右边位置 (j+1)%n 走一步到达 j
            dp[i][j] += dp[i-1][(j+1)%n]
        }
    }

    // 走 n 步后回到原点 0 的方案数
    return dp[n][0]
}

解法二：滚动数组优化

核心思路：

解法一的 dp 数组大小为 (n+1) × n，但每次状态转移只依赖上一行，因此可以使用两个一维数组滚动更新，将空间压缩到 O(n)。

prev[j]：上一步（走 i-1 步）在位置 j 的方案数

curr[j]：当前步（走 i 步）在位置 j 的方案数

每轮结束后用 curr 替换 prev，继续下一轮迭代。

复杂度分析：

时间复杂度：O(n²)，其中 n 为圆环大小，共 n 步，每步遍历 n 个位置

空间复杂度：O(n)，其中 n 为圆环大小，仅使用两个长度为 n 的滚动数组

class Solution {
    public int backToOrigin(int n) {
        // prev 表示上一步各位置的方案数
        int[] prev = new int[n];
        // 初始状态：走 0 步，在位置 0
        prev[0] = 1;

        for (int i = 1; i <= n; i++) {
            int[] curr = new int[n];
            for (int j = 0; j < n; j++) {
                // 从左边位置 (j-1+n)%n 走一步到达 j
                curr[j] += prev[(j - 1 + n) % n];
                // 从右边位置 (j+1)%n 走一步到达 j
                curr[j] += prev[(j + 1) % n];
            }
            // 滚动更新
            prev = curr;
        }

        // 走 n 步后回到原点 0 的方案数
        return prev[0];
    }
}

func backToOrigin(n int) int {
    // prev 表示上一步各位置的方案数
    prev := make([]int, n)
    // 初始状态：走 0 步，在位置 0
    prev[0] = 1

    for i := 1; i <= n; i++ {
        curr := make([]int, n)
        for j := 0; j < n; j++ {
            // 从左边位置 (j-1+n)%n 走一步到达 j
            curr[j] += prev[(j-1+n)%n]
            // 从右边位置 (j+1)%n 走一步到达 j
            curr[j] += prev[(j+1)%n]
        }
        // 滚动更新
        prev = curr
    }

    // 走 n 步后回到原点 0 的方案数
    return prev[0]
}

相似题目

题目	难度	考察点
62. 不同路径	中等	动态规划 / 路径计数
63. 不同路径 II	中等	动态规划 / 障碍物处理
70. 爬楼梯	简单	动态规划 / 计数 DP
935. 骑士拨号器	中等	动态规划 / 棋盘路径计数
688. 骑士在棋盘上的概率	中等	动态规划 / 概率 DP
837. 新 21 点	中等	动态规划 / 概率 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/89102112