dp实现关于子序列问题
1.最长上升子序列的长度
代码实现：
状态转移方程：
len(1)=1;
len(k)=max{len(i):1<i<k且ak>ai且k!=1}+1;
2.上升序列的最大和
注意：最长的上升子序列的和不一定是最大
代码实现：
状态方程：
s(1)=a[1];
s(k)=max{s(i):1<i<k且ak>ai且k!=1}+a[k];
3.最长公共子序列的长（两个串）
①最优子结构性质定理：
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则
(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。
(2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。
(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。
②状态方程：
代码实现：