【Leetcode】机器人到达指定位置方法数（动态规划）_机器人达到指定位置方法数 leetcode-CSDN博客

本文链接：https://blog.csdn.net/Fire_to_cheat_/article/details/110440008

Foreword

原版是 https://www.notion.so/bryce1010/2b4b9e98bb34422084d3cf3f84534df3，原版查看体验更佳。

Resources

题目

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

分析

这道题不难，但是总结了用暴力递归解决的方法优化为动态规划的套路。

复习一下，个人经验来说，暴力递归的优化有两个主要方法：

记忆化搜索
https://oi-wiki.org/dp/memo/
动态规划（动态规划还可以视情况压缩空间）

解法1：暴力递归

首先介绍一下本体暴力递归方法。

如何才能尝试遍历所有的走法，如果当前来到cur位置，还剩rest步要走，那么有以下情况：

cur位置为0，那么下一步为(1, rest-1)
cur位置为N，那么下一步为(N-1, rest-1)
以上两种情况都不是，那么cur可以往左走为(cur-1,rest-1)
cur也可以往右走(cur+1,rest-1)

如果rest=0的时候，cur刚好在P，那么就是一次符合规则的走法，否则不符合。

详细代码：

public int walk(int N, int cur, int rest, int P){
	if(rest==0){
		return cur==P?1:0;
	}
	
	if(cur==1){
		return walk(N,cur+1,rest-1,P);
	}
	if(cur==N){
		return walk(N,cur-1,rest-1,P);		
	}
	return walk(N,cur-1,rest-1,P)+walk(N,cur+1,rest-1,P);
}

一旦写好了上面的尝试函数，那么后面的优化过程全是套路。下面总结暴力递归到动态规划的优化过程。

由于暴力递归的时间复杂度是 递归深度*每次递归运算复杂度，一般来说会比动态规划的复杂度更高很多。

解法2：动态规划

动态规划的三部曲

无后效性
重叠子问题
最优子结构

首先根据walk函数的含义，分析一下整个递归过程是否具有后效性。无后效性的意思是指一个递归状态的返回值，与怎么到达这个路径的状态无关（也就是可以一个状态可以由多个递归路径到达）。

在本题中，我们可有简单分析一下，本题无后效性。

在确定无后效性后，下面都是套路就能将暴力递归优化为动态规划

找到可变参数可以代表一个递归状态，也就是哪些参数确定了，那么返回值就确定了，本题中的可变参数只有两个(cur, rest)
把可变参数映射为一张表，有1个可变参数就映射为1维表，有2个可变参数就映射为2维表
根据递归过程，确定base case，把这张表最简单、不依赖其他位置的值先填好
根据递归过程，将非base case，分析转换关系计算填写完整

分析出动态规划转换方程

if cur == 1:
	dp[rest][cur]=dp[rest-1][2]
if cur == N:
	dp[rest][cur] = dp[rest-1][N-1]
else:
	dp[rest][cur] = dp[rest-1][N-1]+dp[rest-1][N+1]

详细代码为：

public int wat2(int N, int M, int K ,int P){
	
	int[][] dp = new int[K+1][N+1];
	dp[0][P]=1;
	for(int i=1;i<=K;i++){
		for(int j=1; j<=N; j++){
			if(j==1) dp[i][j]=dp[i-1][2];
			else if(j==N) dp[i][j]=dp[i-1][N-1];
			else dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
		}
	}
	return dp[K][M];
}

还可以继续路径压缩优化：矩阵的最小路径和这里进行了路径压缩的详细总结

int[] dp = new int[N+1];
dp[P]=1;
for(int i=1;i<=K;i++){
	int leftUp = dp[1];
	for(int j=1;j<=N;j++){
		int tmp = dp[j];
		if(j==1) dp[j] = dp[j+1];
		else if(j==N) dp[j]=leftUp;
		else dp[j]= leftUp + dp[j+1];
	}
}