一个算法题, 规定机器人在一个区间内行动一定步数来到某个位置,使用递归算法解决

Luosu

正在学习递归算法,想用递归算法解决这个问题.
想了一个早上,但还是没明白问题出现在哪, 希望有大佬指点一下.


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

若规定机器人必须走k步, 最终来到p位置(p在1~n中)
给定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);
}

CEveryC

下下周看看