动态规划（四）：投资问题、背包问题、最右二叉搜索树问题

一、投资问题

收益矩阵

重新思考问题：

设置递推方程：
和的最大值也就是

对于分配的每一种情况求一下最大分配的值

到第三个项目的时候，把前两个项目当成第一部分，第三个项目当成第二个可分配的部分
第三个的时候，2,0；1,1；0,2 只是分配到了两个部分，第一个给第一部分，第二个给第二部分。

现在就变成，前一部分份2W最优，个当前3分0W；前一部分最优分1W，3份1W；前一部分最优分0W，和当前部分份2W。

备忘录：记录当前收益和当前项目投资的钱数
所以最终最优的收益是：1，0，3，1

二、0/1背包问题

m（i, j）：i 是前面几个物品的都不要了，从i开始要。j是当前背包的容量
m(i,j)可以分为两种情况：要不要当前的物品。若当前物品的超过当前环境荣奶的，那肯定不要。
或者 max ( 不放的价值，放的价值 )
m(n,j)：是考虑最后一个物品的情况

所以从0开始放第一个物品，然后第二个…下面这张图的思路是从最后一个N物品开始选择，其实都是一样的。

时间复杂度的分析

举例说明：i是当前可用的和i之后也能用，j是当前背包的容量
可以根据上面那张图分析出来的解雇把这张表填上

三、最优二叉搜索树

会有找不到的情况，因为可能找的值不在这一棵树上

最优二叉搜索树：左右子树的高度相差不超过1.