（4）动态规划和贪心算法相关题目

（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