递归算法求解简单的区间移动问题

正在学习递归算法, 算法题意如下:

假设有排成一行的n个位置, 即为1到n, n一定是大于或是定义2的值.
开始的时候机器人在其中的m位置上,m一定是1~n中的一个
如果机器人来到1位置,下一步只能往右来到2位置;
若在n位置, 下一步只能往左来到n-1位置
若在中间,下一步可以选择往左或是往右走

若规定机器人必须走k步, 最终来到p位置(p在1~n中), 每步只能走1个位置
给定4个参数n, m, k, p . 返回可行的方法数

#include "stdafx.h"
#include <iostream>

//当前位置与剩余步数的值,也用于确定数组大小
#define M 5
#define K 5

int walkCache(int n, int cur, int rest, int p, int dp[][K + 1]){
    if (dp[cur][rest] != -1){ //如果dp已经更新,直接返回
        return dp[cur][rest];
    }

    if (rest == 0){ //结束标志
        dp[cur][rest] = cur == p ? 1 : 0;
        return dp[cur][rest];
    }

    if (cur == 1){ //左边界
        dp[cur][rest] = walkCache(n, 2, rest - 1, p, dp);
        return dp[cur][rest];
    }

    if (cur == n){ //右边界
        return walkCache(n, n - 1, rest - 1, p, dp);
    }

    //中间
    dp[cur][rest] = (walkCache(n, cur + 1, rest - 1, p, dp) + walkCache(n, cur - 1, rest - 1, p, dp));

    return dp[cur][rest];

}

int waysCache(int n, int m, int k, int p){
    if (n < 2 || k < 1 || m < 1 || m> n || p < 1 || p > n){
        return 0;
    }

    int dp[M + 1][K + 1];
    memset(dp, -1, sizeof(dp));

    return walkCache(n, m, k, p, dp);
}

int main(){
    std::cout << waysCache(10, M, K, 6);
}

代码可以运行,但结果出错, 调试过程中发现
每次执行到 (walkCache(n, cur + 1, rest - 1, p, dp) + walkCache(n, cur - 1, rest - 1, p, dp))
就会返回一个较大的值给dp[cur][rest], 在最后dp[cur][rest]的值会变的很大, 越界成为负数.

期望返回一个int, 表示当前状态的可行方法数.
我不太清楚是递归思路算法错误,还是具体的代码出现了错误.

我写的和你写的略有不同，但都是递归，你可以参考一下我写的

#include <iostream>

int walk_start(int n,int m,int k,int p);
int walk_left(int n,int m,int k,int p);
int walk_right(int n,int m,int k,int p);
int sum=0;
using namespace std;

int main()
{
    int n,m,k,p;

    cin >> n >> m >> k >> p;
    walk_start(n,m,k,p);

    cout << sum << endl;
    return 0;
}

int walk_start(int n,int m,int k,int p)
{
    walk_left(n,m,k,p);
    walk_right(n,m,k,p);
    return sum;
}
int walk_left(int n,int m,int k,int p)
{
    k--;
    m--;

    if(k==0&&m==p)
        return sum++;
    else if(k==0&&m!=p)
        return 0;
    else if(k!=0&&m<1)
        return 0;
    else
    {
        walk_left(n,m,k,p);
        walk_right(n,m,k,p);
        return 0;
    }
}
int walk_right(int n,int m,int k,int p)
{
    k--;
    m++;

    if(k==0&&m==p)
        return sum++;
    else if(k==0&&m!=p)
        return 0;
    else if(k!=0&&m>n)
        return 0;
    else
    {
        walk_left(n,m,k,p);
        walk_right(n,m,k,p);
        return 0;
    }
}