题目来源
题目详情
圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。
输入: 2
输出: 2
解释：有2种方案。分别是0->1->0和0->9->0
题解分析
本题考察的是动态规划。
如果你之前做过leetcode的70题爬楼梯，则应该比较容易理解：走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。
因此，若设(dp[i][j])为从0点出发走i步到j点的方案数，则递推式为：
[dp[i][j] = dp[i-1][(j+1)%len] + dp[i-1][(j-1+len)%len] ]
ps:公式之所以取余是因为j-1或j+1可能会超过圆环0~9的范围
package com.walegarrett.programming;
import org.junit.Test;
/**
* @Author WaleGarrett
* @Date 2022/4/6 16:16
*/
public class Addition_2 {
/**
* 圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。
* 输入: 2
* 输出: 2
* 解释：有2种方案。分别是0->1->0和0->9->0
*/
public int circleSteps(int n, int k){
// 圆环中有n个节点，走k步回答原点有几种走法
// 走k步走到0的走法=走k-1步走到1的走法 + 走k-1步走到num-1的走法
// dp[i][j]表示走i步走到j点的走法种类
// dp[i][j] = dp[i-1][(j+1)%len] + dp[i-1][(j-1+len)%len]
int[][] dp = new int[k+1][n];
dp[0][0] = 1;
for(int i=1; i
Original: https://www.cnblogs.com/GarrettWale/p/16107220.html
Author: Garrett_Wale
Title: LeetCode-补充题2. 圆环回原点问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583190/
转载文章受原作者版权保护。转载请注明原作者出处！