暴力递归到动态规划--机器人移动
有N格（标号1~N），start为机器人初始位置，end为机器人目的地，k是机器人一定要走的步数。求从start开始走完k步到end的方案数。
解法：
1）暴力递归，代码如下，解释省略，这是最简答的思路。
暴力递归问题在于会有许多重复的操作，如下图，多次暴力展开相同的情况。
这也是暴力递归改动态规划唯一的理由，我们需要对走过的路进行存储，遇到时就可以直接用。
2）优化1：记忆化搜索
利用一个缓存ache，遇到一种情况先看缓存中有无次记录，有则直接拿取，无则计算并存储进表。
虽然没有对递归结构进行更改，仅仅是利用一个缓存，而缓存数据之间的关系也没有考虑，但这也体现了动态规划的思想。
3）优化2：更改缓存结构
map存储数据似乎大题小用，而且map查询的常数时间也不小。这里直接改用数组来缓存，至此我们没有用到转移函数，但动态规划雏形已经显现。
4）最终优化
下图cur为当前所处位置，rest为所剩步数。（N=7，start=2，end = 3，k=5）
即最终调用函数func4（2,5）。
第一行不使用，而第一列我们可以通过初始条件来计算结果。剩0步的情况下，当前位置是目标位置就是1（即成功数），不是目标位置就肯定是0。
得出这个之后，我们就要想怎么利用依赖关系推出星号位置的值。
依赖关系：（由递归式推出）
1）第一行的值只依赖其左下角的值，因为当前位置为1，只能够往前走，即cur+1，而rest每走一步都要减一。
2）对于最后一行cur为7，同理，只可以往后退，所以最后一行元素依赖其左上角。
3）而中间的元素因为可进可退，所以依赖于左上角+左下角。
找出依赖关系后我们就可以找到填值的顺序，这里是一列一列填写。这个填值尝试的规则，就是转移函数的形式。
·转移函数得出方法：
1）先找出固定量和可变量，以影响结果的可变量确定表的维数，以可变参变化范围确定表的大小。
2）给出一组具体参数例子。
3）填好不依赖其他任何位置的格子，确定表中最终目标位置（即看主函数怎么调用）
4）分析普遍位置依赖（看递归函数怎么调用，依赖关系就怎么确定）
均得出结果