动态规划就是为了优化暴力尝试的。

01：08：00

题一： 求n!

启发意义

题目二：汉诺塔问题！

从3层到n层

尝试的思路，总能写出来。

题目三：打印一个字符串的所有子串

还是找试的感觉

题目四：打印一个字符串的全排列

自己去式，过

题目五：母牛生牛问题 fn = fn-1 + fn-3

题目七 矩阵中 最短路径和

怎么从递归试出动态规划

面试中没见过的动态规划问题，先写出递归，从递归到动态规划是高度套路的，比较简单。

有些方法改不出动态规划：比如汉诺塔问题（因为没有重复问题），前面的选择会影响后面的，比如N皇后问题，这称为有后效性。

最短路径和为什么能改出动态规划，因为比如f(0,0) 到 f(1,1) 从f(0,1) 和f(1,0)去往f(1,1)不影响f(1,1)的值，这称为无后效性。

查表的表的维数怎么确定？

可变参数是1个，就是数组；

可变参数是2个，就是矩阵；

可变参数是3维的，就是3维表。

表中的值如何确定？

• 把你需要的位置点出来
  • f(0,0)
• 回到base中，把不依赖的位置设置好
  • 对于这个题就是最后一行和最后一列，求出
• 分析一个普遍位置是怎么依赖的，确定计算顺序
  • 这题就是从右往左，从下往上

先干嘛？

• 先写出尝试(暴力递归)版本

  • 这是最重要的，没有任何东西可以替代这个

• 分析可变参数，哪几个可变参数可以代表返回值的状态

  • 可变参数是几维的，它就是一张几维表

逆着回去，就是我填表的顺序，暴力递归就这么被改成动态规划；

你不要强记什么转移方程，你搞不明白，动态规划就是这么来的；

转移方程怎么来的，递归来的，你把递归写清楚，你才知道它怎么转移来的；

动态规划就是空间换时间，一个非常傻白甜的技术，没有什么内容；

你怎么试（写出 递归）是最重要的；

以后的优化的过程就是搭积木。

题目八 再看一道

来到了i位置，前一步传过的和为sum ,目标是aim ，返回第i位置开始能否累加到目标数字。

分析可变参数的变化范围，要考虑到边界。

这个得会。