70.爬楼梯的扩展
-
三角形最小路径和 记忆化搜索的写法，每次两个递归，时间复杂度是2的n次方 要想省空间复杂度，可以直接改传入的数组，比如倒着求之类的
-
最大子序和dp的题，要看不同的排列组合，是不是不同的解。比如1，1，2和2，1，1是不是同一个解
-
零钱兑换，eg：1，2，5元兑换成11元 1、递归，下图是递归树变负数，表示不合法，0表示正好是解，深度表示零钱个数 2、就是广度优先遍历，一层一层遍历，找到第一个值是0的，层数就是最少的硬币数dp方程，找f(n-k)的最小值，k是1，2，5，最后加一步
看的别人的，很强>>> dp模板： 1､找子问题， 2､定义状态数组 3､定义dp方程状态数组含义不一样，dp方程也不一样，可以是自顶向下，也可以是自底向上 空间复杂度可以有不同方案： 1､状态数组为子问题的个数，通常为二维数组， 2､二维状态数组降成一维 3､一维数组降成滚动数组。 4､直接在入参数组上改，不用另外申请空间。
- 打家劫舍用两个int存
- 打家劫舍 II