（1）最长公共子序列
实现过程中需要维护两个格外的表，一个是b,一个是c.表b[i,j]存储这指向方向，是计算c[i,j]时所选择的子问题的最优解，C[m,n]中记录了LCS的长度。时间复杂度为O(mn)；在构造LCS的过程中，从b[m,n]开始，依次寻找方向，打印出对对应的字符。
其状态转移方程为
LCS状态转移方程
算法具体过程为：
LCS具体流程
相关代码见：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/DynamicProgramming/LongCommonSeq.java
(2)求一个数组的最长递减子序列
比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}。
算法思路：原数组与降序排序后的数组的最长公共子序列。
(3)求数组中的所有递增子序列
对于一个数组{1,2,3}它的子数组有{1,2}，{1,3}{2,3}，{1,2,3}，元素之间可以不是连续的，对于数组{5,9,1,7,2,6,3,8,10,4}，升序子序列有多少个？
算法思路：当前数组与递增数组的最长公共子序列算法。辅助数组里大于1的都算。
（4）剪绳子问题（贪心）
算法思路：n>=5时，多剪3的绳子。N=4时剪两个2.
（5）背包问题
1、0-1背包
判别条件v[i][0]=v[0][j]=0;v[i][j]=v[i-1][j] 当w[i]>j；v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} 当j>=w[i]
相关代码见：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/DynamicProgramming/Bag0_1.java
2、分数背包
贪心，选单位价值最大的
3、完全背包问题
（6）最大连续乘积子串
假设数组为a[]，直接利用动态规划来求解，考虑到可能存在负数的情况，我们用maxend来表示以a[i]结尾的最大连续子串的乘积值，用minend表示以a[i]结尾的最小的子串的乘积值，那么状态转移方程为：
maxend = max(max(maxend * a[i], minend *a[i]), a[i]);
minend = min(min(maxend * a[i], minend *a[i]), a[i]);
初始状态为maxend = minend = a[0]。
（7）最大连续和字串
Max = max(max+ai;ai)，以上为不限制字符串长度，若限制字符串长度则需要通过滑窗实现。
相关代码见：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/DynamicProgramming/MaxSum1.java;
https://github.com/yuanfuqiang456/LeetCode/blob/master/src/DynamicProgramming/MaxSum2.java
网友评论