最近开始学习动态规划算法,我的理解是动态规划算法是一个用空间换时间的算法,常用在一些求最解、计数、判断有无等问题中,且这些问题都存在大量重复的计算。
动态规划的思想就是将已经计算过的数据存储起来,在下次用到时可以直接取用,这样就消除了重复计算。而且这也是体现“动态”的地方,就是能根据之前情况进行灵活处理。
在思考动态规划相关问题时,我自己通常主要考虑四个问题:
- 这个问题的最后一步是什么;
- 倒数第二步我会怎么做;
- 我需要存储什么值;
- 怎样利用这些已经存储的;
比如,一个典型的动态规划的问题:有如下数组,a:[3,-1,2,5,-7,9],求其中连续的子区间和的最大值。
按照上述的问题,我先思考最后一步我会怎么计算。因为是连续的子区间,所以我会先找这个连续子区间的最后一个元素i,因为这个子区间的最大长度不可能超过 i 。所以,我最后一步会研究F(5),表示以a(5)为最后一个元素的子区间中各元素和的最大值。
接下来我会研究第二步,因为是连续子区间,所以我再会比较:F(4)+a[5] 和 F(4) 的大小,大的作为F(5)的值,即:
F(5) = max(F(4),F(4)+a[5]);
所以我们需要开一个数组s[5],存储每个元素结尾的子区间的最大值;
如何利用已经存储的值?看上面的式子:F(5) = max(F(4),F(4)+a[5]) ,可以得到状态转换方程:
F(i) = max (F(i-1)+a[i],F(4)).
所以可以得到如下代码:
go 语言实现
func maxSubArray(nums []int) int {
res := nums[0]
for i:=1;i<len(nums);i++ {
if nums[i-1] > 0 {
nums[i] = int(math.Max(float64(nums[i]),float64(nums[i]+nums[i-1])))
}
res = int(math.Max(float64(nums[i]),float64(res)))
}
return res
}