(T1)机器人达到指定位置方法数【左程云：暴力递归-＞动态规划】

题目描述：

来源：机器人达到指定位置方法数__牛客网 (nowcoder.com)

解题思路 

【1】递归

主要就是通过尝试的方法举出几个例子去构造

以下代码不能通过测试样例。

#include using namespace std;
int process1(int,int,int,int);
int ways1(int N,int start,int aim,int K){
	
	return process1(start,K,aim,N);
}
//当前位置cur
//还有rest步需要走
//最终的目标是aim
//有哪些位置？1~N
//返回：从cur出发，走过rest步之后，最终停在aim的方法数 
int process1(int cur,int rest,int aim,int N){
	if(rest==0){    //如果剩余步数为0，代表走完了，如果到达aim返回1
		return cur==aim?1:0;
	}
	if(cur==1){    //如果在位置1，只能往右走
		return process1(2,rest-1,aim,N);
	}
	if(cur==N){    //如果在位置N，只能往左走
		return process1(N-1,rest-1,aim,N);
	}              //如果在中间位置，既可以往左，也可以往右
	return process1(cur-1,rest-1,aim,N)+process1(cur+1,rest-1,aim,N);
	
}
int main(){
	int N,M,K,P;
	
	cin>>N>>M>>K>>P;
	
	int ans=ways1(N,M,P,K);
	
	cout<

在提交系统上会显示运行超时，因为这段代码的时间复杂度相当之高，具体可以画递归树去分析。

问题1：这段暴力递归的高复杂度体现在哪里？

仅仅到达第三层就已经出现了两个重复元素，第三层中cur到达这两个3位置时process1的处理方式和返回值将是完全一样的，因为他们的cur都为3、rest都为3步、aim都为6、N都为7（四个参数完全一样），这就产生了重复计算。所以我们希望假使四个参数曾出现过就不要再重复处理了，换言之，每种参数的process1只处理一遍就好了，之后再次出现时只需要调用先前处理好的结果。于是我们可以得到第一种优化方式。

【2】（优化）傻缓存法

基于上述想法，我们建立一张(N+1)*(K+1)大小的缓存表dp（用范围dp[1~N][0~K]），去存process2()函数的返回值结果。

问题2：怎么就知道缓存表是这么建的？为什么是二维？为什么两个维分别是cur、rest?

这个问题还是需要回到递归方法去看，首先在递归方法中关键问题在于process1函数的重复计算，我们想想什么导致process1的返回值不一样，这是传入process1的参数决定的，cur,rest,aim,N这四个参数中aim,N这两个参数是一直不变的，变化的是cur和rest，我们就可以说最后导致process1的返回值不一样是因为cur和rest是不断变化的，由此就解决了“缓存表该建成几维的和维度元素怎么取”的问题。

#include using namespace std;
long long int process2(int,int,int,int,vector>&);
long long int ways2(int N,int start,int aim,int K){
	//创建一张（N+1）*（K+1）大小的缓存表，用来记录已经算过的process2()函数的返回值 
	vector> dp(N+1,vector(K+1,-1));
	//初始化dp
	//dp[cur][rest]==-1 	-> process2(cur,rest)之前没算过 
	//dp[cur][rest]！=-1 	-> process2(cur,rest)之前算过
	
	return process2(start,K,aim,N,dp);
}
//cur的范围  1~N 
//rest的范围 0~K 
long long int process2(int cur,int rest,int aim,int N,vector> &dp){
	//之前算过 ,直接用 
	if(dp[cur][rest]!=-1){
		return dp[cur][rest];
	}
	//之前没算过，就算 
	 long long int ans=0;
	
	
	if(rest==0){
		ans= cur==aim?1:0;
	}else 
	if(cur==1){
		ans=process2(2,rest-1,aim,N,dp);
	}else
	if(cur==N){
		ans= process2(N-1,rest-1,aim,N,dp);
	}else
	ans=( process2(cur-1,rest-1,aim,N,dp)+process2(cur+1,rest-1,aim,N,dp) )% 1000000007;
	//这里 % 1000000007是因为 ans太大了，已经超出了long long int的范围 
	//根据分配律 (ans1+ans2+ans3)%x  等价于   ans1%x + ans2%x ans3%x
	
	dp[cur][rest]=ans;
	return ans;
	
}
int main(){
	int N,M,K,P;
	
	cin>>N>>M>>K>>P;
	
	long long int res=ways2(N,M,P,K);
	
	cout< 
这个时候已经是动态规划了，是一种自顶向下的动态规划，每一种情况只算了一遍。自顶向下的动态规划也经常被称为记忆化搜索（Memoization），简言之，记忆化搜索=>搜索+记忆表。
 
运行结果：
 
 
 
【3】（二次优化）
 
 尽管记忆化搜索已经足够高效率了，但还有几个问题：
 
1、对于较大的数据量会导致函数递归调用的层次过多，函数调用栈空间不足，从而发生栈溢出；
 
2、函数的递与归的过程本身也会消耗时间，在递的过程中会把函数的一些信息放入函数栈中，归的过程会传递返回值并且把本次调用的函数的相关信息从函数栈中移除，尽管栈的push()与pop()操作均为常数阶，但当递归的规模足够大时还是会消耗不少的时间。
 
问题3：看来记忆化搜索的不足主要集中在递归上，能不能不用递归，直接在一张二维表上完成搜索和记忆的功能？
 
我们画个图分析一下：
 
（图1）
 
 
现在假设有1~5个位置，可以走6步，start在2，aim在4。建立一张（N+1）*（K+1）的二维表dp，这张表的每个格子代表来到该格子对应的cur和rest时的方法数，怎样去填这张表？我们同样是回到暴力递归去看，
 
第一步（蓝色）：先找basecase，因为 basecase基础值+填表规律=>求解出整张表，在暴力递归中发现rest==0,只有cur==4时方法数为1，其余为0。
 
if(rest==0){    //如果剩余步数为0，代表走完了，如果到达aim返回1
	return cur==aim?1:0;
}
 
第二步（绿色）：在这张表中，我们最终想要的是啥？在暴力递归中看主函数怎么调，主函数调用的是（start,K）的返回值，（start,K）位置就是最后我们最终想要的结果。此例中为（2，6）。
 
int ways1(int N,int start,int aim,int K){
	
	return process1(start,K,aim,N);
}
 
 第三步：分析普遍位置是怎么依赖的。还是回到暴力递归，发现依赖关系：
 
如果cur==1，那么（1，rest）由（2，rest-1）得到；
 
如果cur==N，那么（N，rest）由（N-1，rest-1）得到；
 
如果cur!=1 && cur!=N，那么（cur，rest）由（cur-1，rest-1）+（cur+1，rest-1）得到；
 
if(rest==0){    //如果剩余步数为0，代表走完了，如果到达aim返回1
	return cur==aim?1:0;
}
if(cur==1){    //如果在位置1，只能往右走
	return process1(2,rest-1,aim,N);
}
if(cur==N){    //如果在位置N，只能往左走
	return process1(N-1,rest-1,aim,N);
}              //如果在中间位置，既可以往左，也可以往右
return process1(cur-1,rest-1,aim,N)+process1(cur+1,rest-1,aim,N);
 
以上三步体现为（图1），接着我们可以把整张表填好，如（图2）。
 
（图2）
 
 
有了 basecase基础值 和 填表规律，接下来就是把它们转化为代码描述就解决了
 
（最终版代码）
 
#include using namespace std;
long long int process2(int,int,int,int,vector>&);
long long int ways3(int N,int start,int aim,int K){
	//创建一张（N+1）*（K+1）大小的表,该表直接记录达到（cur,rest）处的方法数 
	vector> dp(N+1,vector(K+1,0));
	
	//第一步：把基础情况填好，也就是对应暴力递归中的跳出条件
	dp[aim][0]=1; //rest为0的这一列，只有cur停在aim处才说明最后到达终点，方法数为1，该列其余位置方法数为0，dp[除了aim位置][0]=0
	
	//第三步：开始填表 ，从上往下，再从左往右 
	for(int rest=1;rest<=K;rest++){  //rest为列 
		dp[1][rest]=dp[2][rest-1];		//第一行元素 只依赖于该元素最近的左下元素 
		for(int cur=2;cur>N>>M>>K>>P;
	
	long long int res=ways3(N,M,P,K);
	
	cout< 
 
运行结果：
 
 
 
此文章用作学习过程的记录，参考的是左程云老师讲的动态规划的课程 ，文章中的例子也均为老师上课举的例子，图片为本人重新绘制，推荐大家亲自去听一听，会有很大收获。如有问题请在评论区提出（虽然我不怎么看），欢迎大家讨论，谢谢大家。