左神初级算法课程第八讲笔记-贪心、递归

金条切分题：

金条切分题

类似于哈夫曼编码，将所有节点生成一棵树，计算所有非叶节点的和使其最小

哈夫曼编码

解题思路：用小根堆解决，每次从小根堆中拿出两个最小的。类似这种总代价分割成子代价的和，可以用贪心策略

项目问题：

项目问题

生成一个大根堆和一个小根堆，小根堆放未解锁的项目，大根堆放解锁的项目，小根堆按花费排列，大根堆按收益排列。做项目时弹出大根堆中堆顶，然后把此时小根堆中能做的项目弹到大根堆，再继续做项目，如此反复。

会议宣讲问题：

会议宣讲问题

贪心策略选择：按哪个项目早结束安排

贪心策略选择

暴力递归：

暴力递归

动态规划：

动态规划

题目一：求n！

题目二：汉诺塔问题，打印n层汉诺塔从最左边移到最右边的全部过程，一共要2^n-1步（T(N)=2T(N-1)+1）

①1~n-1移到中间杆上②把n移到目标杆③把1~n-1移到目标杆

题目三：打印字符串的所有子序列（类似问题还有全排序）

打印字符串的所有子序列

题目四：母牛生母牛问题F(N)=F(N-1)+F(N-3)，类似于斐波那契数列

母牛生母牛问题

问题五：二维数组路径和

二维数组路径和

这题可以由暴力递归改成动态规划（但有些题不能改，例如汉诺塔问题）

暴力枚举思路，还是递归

暴力枚举复杂度太高，因为在计算过程中有些位置的最短路径和被计算了多次，重复计算浪费较高，解决思路是把这些值放到缓存中，建立一个map然后每次都查找，这叫记忆化搜索方法；另一思路是改动态规划：

有重复状态，而且重复状态与到达路径无关，这样的问题可以改动态规划，即无后效性问题。例如这题i，j确定后返回的最短路径值是确定的，与之前如何到达这个i，j点是没有关系的。因此可以生成一个矩阵（即dp），里面放着每个i，j位置的最短路径返回值。dp矩阵中有些位置可以直接得到其返回值，不依赖提问的位置：

dp矩阵

然后依据这些逆向推所求过程。dp都是这样的套路，先写暴力递归，然后改dp

问题六：

dp问题 递归，看湿了

然后根据变化量i和sum建立二维dp矩阵

dp矩阵