动态规划算法--机器人到达指定位置的方法数量-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划算法--机器人到达指定位置的方法数量。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、背景

暴力递归和动态规划的本质是一样的，动态规划就是尝试减少重复计算的技巧而已。这种技巧是一个大型套路，先写出用尝试的思路解决问题的递归函数，而不用操心时间复杂度。

动态规划的优化大致分为三个过程，第一阶段是暴力递归，即不使用任何技巧优化时间复杂度，目的仅仅是通过尝试得到正确的递归函数；第二阶段是记忆化搜索，即将前面计算得到结果记录下来，从而避免后续重复计算造成的超时问题；第三阶段是严格表结构，即采用斜率优化等数学模型来优化时间和空间复杂度，是一种高级的动态规划。

二、动态规划算法步骤

动态规划算法的一般步骤总结如下：

找到什么可变参数可以代表一个递归状态，也就是哪些参数一旦确定，返回值就确定了
把可变参数的所有组合映射成一张表，有 1 个可变参数就是一维表，2 个可变参数就是二维表，......
最终答案要的是表中的哪个位置，在表中标出
根据递归过程的 base case，把这张表的最简单、不需要依赖其他位置的那些位置填好值
根据递归过程非base case的部分，也就是分析表中的普遍位置需要怎么计算得到，那么这张表的填写顺序也就确定了
填好表，返回最终答案在表中位置的值

三、机器人到达指定位置的方法数量算法

1.算法问题介绍

假设有排成一行的 N 个位置，记为 1~N（N 一定大于或等于 2）。开始时机器人在其中的 M 位置上(M 一定在 1~N 中)，机器人可以往左走或者往右走，如果机器人来到 1 位置，那么下一步只能往右来到 2 位置；如果机器人来到 N 位置，那么下一步只能往左来到 N-1 位置。规定机器人必须走 K 步，最终能来到 P 位置(P 也一定在1~N 中)的方法有多少种。给定四个参数 N、M、K、P，返回方法数。

【举例】 N=5,M=2,K=3,P=3。上面的参数代表所有位置为 1 2 3 4 5。机器人最开始在 2 位置上，必须经过 3 步，最后到达 3 位置。走的方法只有如下 3 种:

从2到1，从1到2，从2到3
从2到3，从3到2，从2到3
从2到3，从3到4，从4到3
所以返回方法数 3。

N=3,M=1,K=3,P=3 上面的参数代表所有位置为 1 2 3。机器人最开始在 1 位置上，必须经过 3 步，最后到达 3 位置。怎么走也不可能，所以返回方法数 0。

2.算法思路

2.1 暴力尝试

首先用尝试的方法写出暴力递归函数f，f的返回值为方法数。暴力递归之所以暴力，是因为它遇到每一种情况时都需要分析能导致这种情况的子情况。例如 f(rest=4,cur=2) 时，需要调用 f(rest=3,cur=1)和f(rest=3,cur=3)这两种子情况，分析f(rest=3,cur=1)时又要调用f(rest=2,cur=2)；分析f(rest=3,cur=3)时要调用f(rest=2,cur=2)和f(rest=2,cur=4)……到达底层以后再向上回溯汇总方法数。

这种调用方式是树型结构，需要耗费大量时间和空间。时间复杂度为O(2n).

//暴力递归：f函数返回方法数
//N是位置总数，P是最终位置，rest表示剩余步数，cur表示当前位置
int f1(int N, int P, int rest, int cur)
{
	if (rest == 0)//base case 当步数走完，若在P点，返回一个结果
		return cur == P ? 1 : 0;
	if (cur == 1)//若在左边界，只能往右
		return f1(N, P, rest - 1, 2);
	if (cur == N)//若在有边界，只能往左
		return f1(N, P, rest - 1, N - 1);
	//在中间位置时，有向左和向右两种选择
	return f1(N, P, rest - 1, cur - 1) + f1(N, P, rest - 1, cur + 1);
}

2.2 记忆化搜索

分析暴力递归的情况我们很容易发现调用递归函数时，经常会发生重复计算的问题，上例中就发升了连续两次调用f(rest=2,cur=2)函数。所以如果能将这个函数的返回值记录下来，那么在下次调用时就可以节省大量时间。时间复杂度为O(n*k).

使用dp数组来记录返回值，初始化数组为全“-1”，数组中的值记录每种情况下的方法数。

int dp[100][100];
int walkWay(int N, int P, int K, int M)
{
	for (int i = 0; i <= K; i++)
	{
		for (int j = 0; j <= N; j++)
			dp[i][j] = -1;
	}
	return f2(N, P, K, M);
}
int f2(int N, int P, int rest, int cur)
{
	if (dp[rest][cur] != -1)//缓存命中，直接返回方法数
		return dp[rest][cur];
	//缓存未命中,记录
	if (rest==0)//base case
	{
		dp[rest][cur] = cur == P ? 1 : 0;
		return dp[rest][cur];
	}
	//有路可以继续走
	if (cur == 1)
	{
		dp[rest][cur] = f2(N, P, rest - 1, cur + 1);
		return dp[rest][cur];
	}
	if (cur == N)
	{
		dp[rest][cur] = f2(N, P, rest - 1, cur - 1);
		return dp[rest][cur];
	}
	dp[rest][cur] = f2(N, P, rest - 1, cur - 1) + f2(N, P, rest - 1, cur + 1);
	return dp[rest][cur];
}

2.3 严格表结构的动态规划

通过递归的对应关系，很容易列出dp数组的每一个元素。如图所示，当从2出发，走4步到达4位置的走法共有4种。这张dp表就是严格表结构。严格表结构的时间复杂度显然是填表的时间O(k*n)

严格表结构和记忆化搜索最大的区别是：记忆化搜索时不用整理数据间的依赖关系，只需要列出递归函数，并用dp表记录递归函数的返回值即可；严格表结构中则需要弄清楚位置间依赖的顺序。弄清楚了位置间的依赖关系，就不需要使用递归函数了，直接按照依赖关系正序填表即可。动态规划的核心不在于状态转换方程，而是在于明确表结构中元素位置的依赖关系。

四、代码实现如下文章来源地址https://www.toymoban.com/news/detail-791718.html

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
 
int dp[100][100];
int dpWay(int N, int P, int K, int M)
{
	dp[0][P] = 1;
	for (int rest = 1; rest <= K; rest++)
	{
		for (int cur = 1; cur <= N; cur++)
		{
			if (cur == 1)
				dp[rest][cur] = dp[rest - 1][cur + 1];
			else if (cur == N)
				dp[rest][cur] = dp[rest - 1][cur - 1];
			else dp[rest][cur] = dp[rest - 1][cur - 1] + dp[rest - 1][cur + 1];
		}
	}
	return dp[K][M];
}
 
int main()
{
	int N = 5, P = 4, M = 2, K = 4;
	cout << dpWay(N, P, K, M);
}

到了这里，关于动态规划算法--机器人到达指定位置的方法数量的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！