【算法笔记】动态规划--编号动态规划问题
最长递增序列问题
输入:A[1 2…n]
输出:最长递子增序列的长度
1.如何用子问题来表示
(思路上:dp[ i ]:一定包含i 或 可能包含i)
设:dp[ i ]表示以第 i 个元素结尾的最长序列长度
则总问题==max(dp[ i ]),其中i=1,2…n。
2.优化子结构和重叠子问题
3.递归方程的建立
dp[ i ] = max{ dp[ j ](其中j < i且aj < ai)}+1
递归终点:dp[ 0 ] = 1;
4.自底向上的计算
\5. 伪代码
For i = 1 To n
dp[ i ] <~ 0;//初始化
For j = 0 To i-1
if( a[ j ] <= a[ i ] AND dp[ i ] < dp[ j ])
Then dp[ i ] <~ dp[ j ]
dp[ i ] = dp [ i ] + 1
return max(dp[ i ])
6.时间复杂度O(n^2)
7.优化
每次寻找最大dp[ j ]时 时间复杂度 为O(n),若使用堆结构,可以优化到O(logn)
最大子数组问题
问题定义:
输入:A[1..n]
输出:最大子数组
A.暴力求解 O(n^2)
B.分治法:O(nlogn)
(1) 分组:以从中央位置mid=⌊(low+high)/2⌋将A[low..high]划分为两个子数组
则结果只能为三种情况
• 完全位于子数组A[low..mid]中,即low≤i≤j≤mid 。
• 完全位于子数组A[mid+1..high]中,即mid<i≤j≤high。
• 跨越了中央位置mid,即low≤i≤mid<j≤high。
(2) 求解
递归终点:if(low == high)return (low,high,A[low]);
(3) 合并:比较三个和的大小O(1) + 计算crosssum O(n)
伪代码:
所以有递归式T(n)=2T(n/2)+Θ(n)。求解这个递归式,得到T(n)=Θ(nlgn)。
C. 动态规划
上述最大递增序列和问题是不连续最大和的问题,而现在转而研究连续的最大和问题
1.如何用子问题来表示
dp[ i ]表示以 i 结尾的最大子数组
则总问题==max(dp[ i ]),其中i=1,2…n。
2.优化子结构和重叠子问题
3.递归表达式
dp[ i ] = max(dp[ i-1 ] + A[ i ] , A[ i ])
递归终点:dp[ 0 ] =A[ 0 ];
4.伪代码
For i = 0 To n
if i == 0
dp[ i ] <~A[ 0 ];
else
dp[ i ] <~ max( dp[ i-1] + A[ i ] , A[ i ])
summax <~ A[ 0 ];
For i = 0 To n
if dp[ i ] > summax
summax = dp [ i ]
return summax
\5. 时间复杂度:O(n)
【钢条切割问题】
给定一根长度为n英寸的长钢条,求最优切割方案,使得销售收益最大。
注意:不切割也是一种可能方案
1.如何用子问题表示
设dp[ i ]表示前 i 长度的最优切割
其中dp[ 0 ]表示不进行切割
则总问题==dp[ n ]
\2. 优化子结构和重叠子问题
\3. 递归表达式
dp[ i ] = max{dp[ j ] + pi-j (其中 0 <= j < i)}
递归终点:dp[ 0 ] = 0
\4. 时间复杂度分析O(n^2)
\5. 伪代码
For i = 1 To n
dp[ i ] = 0
For j = 0 To i - 1
if dp[ i ] < dp[ j ] + pi-j
dp[ i ] = dp[ j ] + pi-j
return dp[ n ]