美文网首页
动态规划做题笔记_待整理

动态规划做题笔记_待整理

作者: 小碧小琳 | 来源:发表于2018-09-14 10:22 被阅读0次

不同的路径

[LeetCode] Unique Paths 不同的路径

一个非常简单的DP题。分析三要素,写出状态转移方程如下:

f[i][j] = f[i - 1][j] + f[i][j - 1]

根据动态方程,可以知道当前状态由 i-1 行的第j列,与当前行第 i 行的前一列 j-1 决定。
因此,对于f[i - 1][j],需要保存一个一维数组,用来记录前一行每列的最优值。
对于f[i][j - 1]只需要用前一个替换就行。(即上一个循环中的f[i][j])

三角形问题

[LeetCode] Triangle 三角形
DP解决,假设第i,j的最优值为f[i][j],从上往下,第二行开始,状态转移方程为
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + (i,j)

但是因为三角形,每一行数组长度不一样,又要求空间复杂度是O(n),所以按照上一题的解法,是不可行的(因为上一题是维护一个相同shape的数组)。所以第一种方法,就是直接改动三角形数组的值。

但是这种方法,会改动原数据,不完美。于是有第二种方法,复制最后一行数组,在复制的一维数组中,从下往上的运行DP。。具体方法见参考。

最大子数组的和

[LeetCode] Maximum Subarray 最大子数组

Maximum Subarray

举例[-2,1,-3,4,-1,2,1,-5,4]

如果用动态规划做,是比较简单的一道题。

参考soulmachine的LeetCode题解,讲的比较清楚了。

需要比较深刻的理解并总结规律。(这道题只让输出最大和,并没有让同时输出子数列)
对于数组里的一个整数,它只有两种选择 :1、加入之前的SubArray;2、自己另起一个SubArray,作为SubArray的开头。那么什么时候会出现这两种情况呢?

这时候不是说,要判断子数列是否是最大值时再相加。(若是有最大值,在出现的时候,就已经被res保存了,这里只单纯的讨论,这个数要不要加到SubArray中去)

  • 如果SubArray总体和大于0,那么这个子数列对于后续结果是有贡献的。
  • 如果SubArray总体和小于0,那么这个子数列对于后续结果没有贡献甚至有害,此时,我们选择以这个数字作为开始重新另起一个SubArray。

比如,前面数组中,-2小于0,那么这个SubArray加上后面的,也是会损害总体和的。所以应该舍弃,从1开始另起一个SubArray。
1大于0,那么只要是加上后面的说,就一定会使SubArray往好的方向发展。
[1,-3]小于0,所以应该再从4开始。

假设 f[j] 代表当前以第 j 个元素为结尾的SubArray的和,S[j] 代表数组的第j个元素。
那么怎么将上述的解释,转化成状态转移方程呢。

  • 转换一下思路,上面就是对于f[j]来说,就两种可能,一是取f[j-1] + S[j],二是取S[j]。所以直接就是,取其中最大值即可。

  • 最大值,就是在j从0到最后期间,出现的最大值。

于是可以得到状态转移方程:
res为最终结果,cur为当前值
先用sys.maxsize,获得最小整数,对res进行赋值。cur赋初值为0.
Python获取最大最小整数值参考Python 小技巧:Python3 表示最大整数值和浮点数值
于是可以有(C++代码)

        int res = INT_MIN, curSum = 0;
        for (int num : nums) {
            curSum = max(curSum + num, num);
            res = max(res, curSum);

拆分回文串2

[LeetCode] Palindrome Partitioning II 拆分回文串之二
暂时没看懂。。。

最大矩形问题、、、

都是hard题,劝退,劝退。

相关文章

网友评论

      本文标题:动态规划做题笔记_待整理

      本文链接:https://www.haomeiwen.com/subject/ndbgwftx.html