【算法笔记】动态规划--编号动态规划问题

最长递增序列问题

输入: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)

​ 伪代码:

imgimg

imgimg

所以有递归式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)

【钢条切割问题】

img

给定一根长度为n英寸的长钢条,求最优切割方案,使得销售收益img最大。

注意:不切割也是一种可能方案

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 ]