动态规划

暴力递归转动态规划：

1.尝试写出递归

2.记忆化搜索

3.严格表结构

某些问题上记忆化搜索和严格表结构的时间复杂度相同

机器人运动问题：

给定一个int参数n代表了n个位置（n大于1），再给一个int参数s代表机器人所在位置看（范围在1到n）int参数e代表机器人要去的最终位置（范围1到n）int参数k表示机器人必须走k步，机器人可往左走或右走，不可停留在原地，从s走到e必须走k步，求有多少种方法

优化前的递归方法：时间复杂度为O(2^k)

记忆化搜索优化：

寻找可变参数根据可变参数数量制作对应多维数组（或者哈希表）作为缓存结构，初始值为-1

时间复杂度为O(k*n)

严格表结构优化：

根据最初的递归寻找每个位置所依赖的表格位置，例如当k为4，s为2，n为5，e为4时，列出下列表格，行代表剩余步数，列代表所在位置

例题2：

给定一个长度为n的正整数数组，数组的每个位置代表该位置硬币的面值，给定一个值aim，求组成这个aim这个值的最少硬币数

以下为给定例子

递归尝试：

记忆搜索法：增加缓存