看B站视频整理笔记
https://www.bilibili.com/video/av16544031?from=search&seid=15678182469494694104
1.斐波那契数列和动态规划的关系
当n=1,2时fib(n)=1否则fib(n) = fib(n-1)+fib(n-2)
斐波那契数列是一种递归关系，而且是一种重叠的子问题(overlap sub-problem)
假设现在要计算fib（6），计算机会生成两个新的分支，进而产生2^6个分支，非常庞大。
那么f(n-2)会在f(n)和f(n-1)会算两遍，有很多重复的计算，所以要想一种办法将数据进行存储然后代换。
将一些重复子问题计算并保存下来，从而减小空间占用，提高运行速度。
从f(6)算到f(1)复杂度为O(2^n)，如果从f(1)往后算，那么复杂度为O(n)
举例：挑选合适的任务进行执行以得到最优解
设OPT（i）为选中第i个任务后的最优解
OPT(i)=max{vi+opt(prev(i)),opt(i-1)}
进行递归即可，为了防止占用太多的内存空间，可以通过动态规划将程序改为通过数组来存储数据然后循环执行。
例2.从arr={3,34,4,12,5,2}中选择两个数字来实现S=9
还是对每个数字分两种可能性，选和不选。定义函数subset(i,s)
为选择i位数字时，得到和为s的情况
若选择该数字，则为subset(subset(i-1),s-arr[i])否则，不选时为subset(subset(i-1),s) 可能的情况如下：
综上所述
subset(arr,i,s)=选subset(arr,i-1,s-arr[i])不选subset(arr,i-1,s)