动态规划 dynamic programming

作者: logi | 来源:发表于2020-03-28 19:09 被阅读0次

动态规划是什么

求解动态规划的步骤

有一个数组A, 从数组中找到一个序列i->j的和 $M_j$ 的值最大, $M_j$ 表示第j+1个位置前的最大子序列和.

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

目标:
$Max M[j]$
子问题:
$M(j) = max{ (M(j-1) + A[j], A[j] )}$
即检验 $M[j-1]$ 是否大于零，只要大于零加 $A[j]$ ,如果 $M[i-1]<0$ ,那么直接 $M[j]=A[j]$ .

给定一个无序的整数数组，找到其中最长上升子序列的长度。
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

目标:
$Max M[j]$
子问题:
$M(j) = max_{i<j,A[i]<A[j]}{ M(j-1)} + 1$
即,A[j]前的所有子序列的最大长度M(x) 加 1.
还有其他优化算法,见: blog

本文标题：动态规划 dynamic programming

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