分割等和子集

思路:本题可以看成是0-1背包问题,给一个可装载重量为 sum / 2 的背包和 N 个物品,每个物品的重量记录在 nums 数组中,问是否在一种装法,能够恰好将背包装满?dp[i][j]表示前i个物品是否能装满容积为j的背包,当dp[i][j]为true时表示恰好可以装满。每个数都有放入背包和不放入两种情况,分析方法和0-1背包问题一样。 复杂度:时间复杂度O(n*sum)
,n是nums数组长度,sum是nums数组元素的和。空间复杂度O(n * sum),状态压缩之后是O(sum)

阅读更多

求两个字符序列的最长公共字符子序列。

字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。

令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列i=i0,i1,…,ik-1,使得对所有的j=0,1,…,k-1,有xi=yj。

例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。

阅读更多

最长上升子序列问题(LIS)

给定n个整数A1,A2….An,按从左到右的顺序选出尽量多的整数,组成一个上升子序列(子序列可以理解为:删除0或多个数,其他树的顺序不变)。

例如: 序列1,6,2,3,7,5,可以选出1,2,3,5,也可以选出1,6,7,但是前者更长。 选出的上升子序列中相邻元素不能相等。

阅读更多