动态规划学习笔记

       最近开始学习动态规划算法,我的理解是动态规划算法是一个用空间换时间的算法,常用在一些求最解、计数、判断有无等问题中,且这些问题都存在大量重复的计算。

       动态规划的思想就是将已经计算过的数据存储起来,在下次用到时可以直接取用,这样就消除了重复计算。而且这也是体现“动态”的地方,就是能根据之前情况进行灵活处理。

       在思考动态规划相关问题时,我自己通常主要考虑四个问题:

  1. 这个问题的最后一步是什么;
  2. 倒数第二步我会怎么做;
  3. 我需要存储什么值;
  4. 怎样利用这些已经存储的;

     比如,一个典型的动态规划的问题:有如下数组,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
}

    动态规划学习笔记

上一篇:go语言学习-笔记3


下一篇:python-pandas基础数据结构(Series)