机器人到指定位置方法数
【题目】
假设有排成一行的 N 个位置，记为 1~N，N 一定大于或等于 2。开始时机器人在其中的 M 位置上(M 一定是 1~N 中的一个)，机器人可以往左走或者往右走，如果机器人来到 1 位置， 那么下一步只能往右来到 2 位置;如果机器人来到 N 位置，那么下一步只能往左来到 N-1 位置。规定机器人必须走 K 步，最终能来到 P 位置(P 也一定是 1~N 中的一个)的方法有多少种。给定四个参数 N、M、K、P，返回方法数。
【举例】
a.N=5,M=2,K=3,P=3
上面的参数代表所有位置为 1 2 3 4 5。机器人最开始在 2 位置上，必须经过 3 步，最后到达 3 位置。走的方法只有如下 3 种:
1.从2到1，从1到2，从2到3
2.从2到3，从3到2，从2到3
3.从2到3，从3到4，从4到3
所以返回方法数 3。
b.N=3,M=1,K=3,P=3
上面的参数代表所有位置为 1 2 3。机器人最开始在 1 位置上，必须经过 3 步，最后到达 3位置。怎么走也不可能，所以返回方法数 0。
【题解】
总览：暴力尝试为什么要改动态规划？有很多暴力过程，调用过程会大量出现重复解，如果不去空间换时间，时间执行上会有很多无效的解
先看暴力递归代码：
public static int ways1(int N, int start, int rest, int P){
//排除无效情况
if(N<2 || start<1 || start>N ||rest<1|| P<1||P>N){
return 0;
}
return process(N, start, rest, P);
}
// N : 位置为1 ~ N，固定参数
// cur : 当前在cur位置，可变参数
// rest : 还剩res步没有走，可变参数
// P : 最终目标位置是P，固定参数
public static int process(int N, int cur, int rest, int P){
//Base case
//rest==0 当我无路可走的时候，发现居然来到了P位置，那么之前做的决定走的路径就构成了一种有效的解法
if(rest==0){
return cur==P?1:0;
}
//1位置，只能往2位置移动
if(cur == 1){
return walk(N,2,rest-1,P);
}
//N位置，只能往N-1位置移动
if(cur == N){
return walk(N,N-1,rest-1,P);
}
//中间位置的普遍位置i可以移动到i-1位置也可以移动到i+1位置
return walk(N,cur-1,rest-1,P)+walk(N,cur+1,rest-1,P);
}
分析递归方法的时候，可以忽略掉永远不变的固定系数。固定参数其实只是限制条件，参数表中有它们是因为不想让递归函数依赖于函数体外面的东西，不想这么写的话也可以把固定参数抽出来放到函数体外面当成固定变量。
上面递归函数里N和P就是固定参数，只代表一种限制，不代表一种情况，和返回值有关的参数只有可变参数，所以可以把递归过程抽象为f(cur,rest)。
分析递归过程：
假如一共5个位置，初始位置是2，要去的位置是3，要走5步，主函数为f(2,5)，会调用f(1,4)与f(3,4),调用过程如上图所示，可以看到f(2,3)的暴力展开过程重复计算。这就是暴力递归改动态规划的唯一理由，递归函数展开时发现有大量的重复过程。f(2,3)的返回值都是同一个，f(2,3)也不在乎是谁调用的它，只要函数f的参数是2和3，返回值一定是一样的。所以我们不妨用一张表结构把f(2,3)值存下来，下次需要调用f(2,3)的时候直接用这个值即可，这种方法即记忆化搜索，通俗点讲就是傻cache。
记忆化搜索代码写法：
public static int ways2(int N, int start, int rest, int P){
if(N<2 || start<1 || start>N ||rest<1|| P<1||P>N){
return 0;
}
//用HashMap缓存
//用于存储递归结果； f(2,3) -> v存储为 key:"2_3" value:v
HashMap<String,Integer> cache = new HashMap<>();
return f1(N, start, rest, P,cache);
}
public static int waysCache(int N, int cur, int rest, int P,HashMap<String,Integer> cache){
String key = String.valueOf(cur) + "_" + String.valueOf(rest);
// String key = cur + "_" + rest;
// 在进行所有判断之前，用当前cur和rest生成key，查询cache中是否包含这个key，包含的话返回这个key对应的value即可
if(cache.containsKey(key)){
return cache.get(key);
}
// 没有缓存就说明接下来要展开
// 与递归代码相比，在返回之前把所有的结果存到cache里去
int ans = 0;
if(rest==0){
ans = cur==P?1:0;
cache.put(key,ans);
return ans;
}
if(cur == 1){
ans = f1(N,2,rest-1,P,cache);
cache.put(key,ans);
return ans;
}
if(cur == N){
ans = f1(N,N-1,rest-1,P,cache);
cache.put(key,ans);
return ans;
}
ans = f1(N,cur-1,rest-1,P,cache)+f1(N,cur+1,rest-1,P,cache);
cache.put(key,ans);
return ans;
}
ways2() 代码思路：调用递归函数wayscache() 前加入一个HashMap用于存储递归结果， f(2,3) -> v存储为 key:"2_3" value:v。然后在进行所有判断之前，用当前cur和rest生成key，查询cache中是否包含这个key，包含的话返回这个key对应的value即可，就不用进行下面的判断了；而没有缓存接下来要分情况讨论了，每种情况对应的函数值在return之前都已经确定了，所以在return之前把递归得到的结果存到cache里去。
记忆化搜索已经是动态规划了，但没有关心位置之间的依赖关系，它只充当一个傻缓存，不关心大问题是怎么调小问题的，只关心同样的参数组合出现时不会再暴力展开了，而是可以直接从缓存中取它的值。
现在对缓存进行优化，之前使用的HashMap空间肯定够用的，且增删改查都是O(1)的，但是这个O(1)相比于数组读取数据操作的时间常数是大常数。现在再好好分析一下缓存的结构，以得到第二个缓存版本。
Cur范围1到N，rest范围0到k,所以缓存结构没必要哈希表，用二维数组int[][] cache = new int[N+1][K+1];即可（多设置了一行，但第0行不用即可），增加常数时间优势，表结构范围也更清楚。cache初始值设为-1，表示这个位置没算过（不用0表示因为返回值有可能是0）。
public static int f2(int N, int cur, int rest, int P, int[][] cache) {
if (cache[cur][rest] != -1) {
return cache[cur][rest];
}
int ans = 0;
if (rest == 0) {
ans = cur == P ? 1 : 0;
cache[cur][rest] = ans;
return ans;
}
if (cur == 1) {
ans = f2(N, 2, rest - 1, P, cache);
cache[cur][rest] = ans;
return ans;
}
if (cur == N) {
ans = f2(N, N - 1, rest - 1, P, cache);
cache[cur][rest] = ans;
return ans;
}
ans = f2(N, cur - 1, rest - 1, P, cache) + f2(N, cur + 1, rest - 1, P, cache);
cache[cur][rest] = ans;
return ans;
}
f2() 代码思路：在进行所有判断之前，查询cache中当前位置值是否不是-1，不是的话直接返回即可，没算过的话与上面的waysCache() 类似，返回前存值进cache即可。
从始至终都没有提状态转移，暴力递归改动态规划不用列状态转移，一步步尝试过来即可，但最终版本需要关心所有位置是如何依赖下来的，并需要在表中按顺序把所有格子的值填好。
现在结合具体实例分析，还是上面那个例子：一共5个位置，初始位置是2，要去的位置是3，要走5步（数字尽量选小一点，这样便于填表分析），表的位置依赖图解可初始化如下图：
第0行不要，画×，最终要的值是f(2，5)，即从位置2出发走5步。根据basecase分析出哪些位置的值是直接确定的，可得第一列除了f(3,0)是1，其他全是0。现在只剩下一个问题，用什么方式从第一列推到星号的位置。
从上面代码这部分
if (cur == 1) {
ans = f2(N, 2, rest - 1, P, cache);
cache[cur][rest] = ans;
return ans;
}
可以分析出第一行的值等于自己左下角位置的值
根据
if (cur == N) {
ans = f2(N, N - 1, rest - 1, P,cache);
cache[cur][rest] = ans;;
return ans;
}
可以分析出最后一行等于自己左上角的值
第一行和最后一行位置依赖如上图所示
同理任何一个普遍位置的值等于自己左上角的值加上左下角的值
按照以上规则并按照从左往右的大逻辑把表填完，最终返回dp[start][rest]这个位置的值即可。最终动态规划的代码如下：
public static int waysdp(int N, int start, int rest, int end) {
if (N < 2 || rest < 1 || start < 1 || start > N || end < 1 || end > N) {
return 0;
}
int[][] dp = new int[N + 1][rest + 1];
dp[end][0] = 1;
for (int col = 1; col <= rest; col++) {
dp[1][col] = dp[2][col - 1];
dp[N][col] = dp[N - 1][col - 1];
for (int row = 2; row < N; row++) {
dp[row][col] = dp[row - 1][col - 1] + dp[row + 1][col - 1];
}
}
return dp[start][rest];
}
可以看到从暴力递归一步步优化动态规划时并没有特意的去求状态转移方程，转移方程就是尝试策略。
【总结】
- 首先找到尝试，即暴力递归，在尝试里分清楚可变参数和固定参数是什么。
- 只分析可变参数的组合，有一个可变参数就是一维表，两个可变参数就是二维表，分析组合时根据可变参数的变化范围确定分析表大小。
- 给具体的例子，例如本题位置依赖图解就用了具体的N，s，e，k（抽象参数分析不了，影响直观对应，所以例子用具体参数）。
- 看清楚表中你最终想要的位置在哪，标星号（看函数怎么调来确定）；在表中写下完全不依赖其他位置的值，最简单位置先填好，
- 分析普遍的位置依赖，看尝试方法，看递归函数父过程怎么调子过程，可变参数怎么变
网友评论