【算法笔记】动态规划--编号动态规划问题
最长递增序列问题
输入：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）
伪代码：
.png)
.png)
所以有递归式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 ]