H5W3
当前位置:H5W3 > java > 正文

【Java】动态规划-从暴力递归到动态规划的代码之美(一)

 **动态规划**-对于很多人来说,这是一块很难的知识,
我也是一样,起初很茫然,等接触的多了,自然就理解了。
那下面我们就从一到算法题目开始,看看怎么一步步做到的动态规划。
【题目】
假设有排成一行的N个位置,记为1~N,N一定大于或等于2。
开始时机器人在其中的M位置上(M一定是1~N中的一个),
机器人可以往左走或者往右走,如果机器人来到1位置,
那么下一步只能往右来到2位置;
如果机器人来到N位置,那么下一步只能往左来到N-1位置。
规定,机器人必须走K步,最终能来到P位置(P也一定是1~N中的一个)的方法有多少种。
给定4个参数N、M、K、P,返回方法数。
那么根据以上方法,我们通过暴力递归可以写出如下代码:
/**
* @param currentLocation 机器人的起始位置
* @param rest            机器人还剩rest步
* @param targetLocation  机器人的目标位置
* @param length          有多少个位置
* @return 返回机器人从start位置,经过rest步,到达aim位置,可以行走的路径数量
*/
public static int process1(int currentLocation, int rest, int targetLocation, int length) {
//如果机器人还剩0步要走, 而且当前位置正好是目标位置,那么就返回1,相反则返回0;
if (rest == 0) {
return currentLocation == targetLocation ? 1 : 0;
}
//判断机器人如果当前在最左边的位置,那么机器人只能向右侧行走
if (currentLocation == 1) {
return process1(2, rest - 1, targetLocation, length);
}
//判断机器人如果当前在最右边的位置,那么机器人只能向左侧行走
if (currentLocation == length) {
return process1(length - 1, rest - 1, targetLocation, length);
}
//如果机器人在中间位置,那么机器人既可以向左行走,也可以向右行走
return process1(currentLocation - 1, rest - 1, targetLocation, length)
+ process1(currentLocation + 1, rest - 1, targetLocation, length);
}

本文地址:H5W3 » 【Java】动态规划-从暴力递归到动态规划的代码之美(一)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址