一个环，有n个点, 问从0点出发，经过k步回到原点有多少种方法

小鱼儿 2021-09-19 00:26 282阅读 0赞

一个环，有n个点, 每次只能走一步， 问从原点0出发，经过k步回到原点有多少种方法？

/         \\

/           \\

2  ---------1

现在把环上的点编号为0 到 n-1, 即从0点出发，再回到0点有多少种方法？

我们可以想到，再回到0点可以从右面回来，也可以从左面回来，即先到达旁边的一个点，看看有多少回来的方法即可。所以运用动态规划的思想，我们可以写出递推式如下：

d(k, j) = d(k-1, j-1) + d(k-1, j+1);

d(k, j)表示从点j 走k步到达原点0的方法数， 因此可以转化为他相邻的点经过k-1步回到原点的问题，这样将问题的规模缩小。由于是环的问题， j-1, j+1可能会超出 0到n-1的范围，因此，我们将递推式改成如下：

d(k, j) = d(k-1, (j-1+n)%n) + d(k-1, (j+1)%n);

因为问题从走k步转化为走k-1步的问题，所以在写程序的时候我们就按照k从0开始递增的循环写，这样当计算第k步的时候可以直接使用k-1步的结果。

实例如下， n = 3, k = 4

按照k增大计算

0    1    2  
k=0    1    0    0  
k=1    0    1    1  
k=2    2    1    1  
k=3    2    3    3  
k=4    6    5    5

因为计算第k步只与第k-1步的值有关，因此可以使用两行的数组来存储。代码如下：

/\*\*  
 \* 一个圆环， 有n个点， 从0出发，每次只能走一步，问走k步，有多少种方法可以走回来  
 \*/  
   
\#define N 100  
   
int get\_step\_num(int n, int k)  
\{  
    if (n==1)\{  
        return 1;  
    \}  
   
    if (n==2)\{  
        if (k%2==0)  
            return 1;  
        else   
            return 0;  
    \}  
   
    int arr\[2\]\[N\] = \{0\};  
    int flag = 1, i = 0, j = 0;  
   
    arr\[0\]\[0\] = 1;  
    for (i=1; i<n; i++)\{  
        arr\[0\]\[i\] = 0;  
    \}  
   
    // j is the current step  
    for (j=1; j<=k; j++)\{  
        for (i=0; i<n; i++)\{  
            arr\[flag\]\[i\] = arr\[!flag\]\[(i-1+n)%n\] + arr\[!flag\]\[(i+1)%n\];  
        \}  
        flag = !flag;  
    \}  
      
    return arr\[!flag\]\[0\];  
\}  
   
int main()  
\{  
    int n, k;  
    printf("Please input the number n and the step k:\\n");  
    scanf("%d%d", &n, &k);  
   
    printf("%d\\n", get\_step\_num(n, k));  
   
    return 0;  
\}

\---------------------   
作者：chaoyue1216   
来源：CSDN   
原文：https://blog.csdn.net/chaoyue1216/article/details/8096223   
版权声明：本文为博主原创文章，转载请附上博文链接！