动态规划——回望过去 资讯推荐

动态规划——回望过去

(资料图)

配套视频：动态规划——回望过去_哔哩哔哩_bilibili

主要思想：

“那些忘记过去的人，注定要重蹈覆辙。”

比如说，一共有N个数，第一个数有一个值，第N个数也有一个值，问从第一个数到第N个数的累加和为多少。在这道题中，可以将数组状态设为从1到当前数i的累加和，我们用Si来代表第i个状态，那么Si = Si-1 + Ni就是状态转移的关系式。大体上来讲就是设状态，找关系。

例子解释的很清楚。正如例子所说，B记住了之前的答案“8”，当又多了一个“+1”时，B就直接可以将“8”+“1”。但如果B没有记住之前的答案“8”，那么“B”就只能重新一个一个算了。像这种简单的1+1问题还好，从头算也花不了多长时间，但如果是很麻烦的问题，那记住过往就很重要了。

适用范围：

动态规划多用于求解最值（最优、最大、最小、最长）问题；而且动态规划解决的问题一般是可以分解的，适用于求“n的累加和”，“n的阶乘”这类问题。

题目：

1.过河卒（马拦过河卒）

2.最大字段和

总结：

今天我们聊了聊【动态规划】，它的主旨是将待求解的问题分解称若干个子问题，并存储子问题的解而避免计算重复的子问题，并由子问题的解得到原问题的解。

动态规划多用于求解最值（最优、最大、最小、最长）问题；而且动态规划解决的问题一般是可以分解的。

好啦，关于动态规划就说到这里。这里是康郭聊算法，拜拜！

#注：例题答案请查看视频。

标签：