正在学习递归算法,想用递归算法解决这个问题.
想了一个早上,但还是没明白问题出现在哪, 希望有大佬指点一下.
/*
假设有排成一行的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);
}
|