VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 434|回复: 1

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

[复制链接]
13_avatar_middle
最佳答案
0 
在线会员 发表于 2022-4-13 10:47:57 | 显示全部楼层 |阅读模式
正在学习递归算法,想用递归算法解决这个问题.
想了一个早上,但还是没明白问题出现在哪, 希望有大佬指点一下.


/*
假设有排成一行的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);
}





上一篇:程序从C# 移植到 C++CLR看不懂错误提示
下一篇:这道oj题怎么补充代码
97_avatar_middle
最佳答案
0 
在线会员 发表于 2022-4-15 18:11:21 | 显示全部楼层
下下周看看
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

×【发帖 友情提示】
1、请回复有意义的内容,请勿恶意灌水;
2、纯数字、字母、表情等无意义的内容系统将自动删除;
3、若正常回复后帖子被自动删除,为系统误删的情况,请重新回复其他正常内容或等待管理员审核通过后会自动发布;
4、感谢您对VC驿站一如既往的支持,谢谢合作!

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号-4 )|网站地图wx_jqr

GMT+8, 2023-12-11 10:51

Powered by CcTry.CoM

© 2009-2021 cctry.com

快速回复 返回顶部 返回列表