动态规划（一）

淡淡的烟草味﹌ 2022-04-11 03:14 182阅读 0赞

视频地址：[https://www.bilibili.com/video/av16544031?from=search&seid=5667814394353431842][https_www.bilibili.com_video_av16544031_from_search_seid_5667814394353431842]

> 斐波那契数列：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]

我们可以看到很多结果重复计算了，有很多重叠子问题。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1][]

可以利用数组存储中间的过程，减少重复计算。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2][]

动态规划例题：

一共有8个任务，每个任务可以赚不同的钱，每个任务不能有时间重叠，现在想要挣更多的钱，该怎么选择任务，最多能赚多少钱。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 3][]

对于每个任务，分为选和不选两种，比如第8个任务:

选择它：4+f\[5\]，4+前面四个任务的最大值，由于6、7两个任务和8有重叠部分

不选它：f\[7\]，前面七个任务最大值

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 4][]

#include<cstdio>
    #include<cmath>
    #include<iostream>
    using namespace std;
    int v[9]={0,5,1,8,4,6,3,2,4};
    int pre[9]={0,0,0,0,1,0,2,3,5};
    int f[9];
    int main()
    {
    	f[0]=0;
    	f[1]=5;
    	for(int i = 1; i <= 8; ++i)
    	{
    		f[i] = max(f[i-1],f[pre[i]]+v[i]);
    	}
    	for(int i = 1; i <=8; ++i)
    		printf("%d ",f[i]);
    	return 0;
    }

![20181204162343520.png][]

[https_www.bilibili.com_video_av16544031_from_search_seid_5667814394353431842]: https://www.bilibili.com/video/av16544031?from=search&seid=5667814394353431842
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20220411/a6bf5a64aa9b40c285da74eb24f6316a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1]: /images/20220411/b0a362b9da0a4db3b1915aac631c6f7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2]: /images/20220411/a147a9e5a379488385bb7e9bcd557507.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 3]: /images/20220411/dd55dde328664a81a4bb486a52640e0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 4]: /images/20220411/62e6282770974ebe8789b6f038486d31.png
[20181204162343520.png]: /images/20220411/64eaf7cccd454669af8e1acb70aece1b.png