分割等和子集

思路:本题可以看成是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,但是前者更长。 选出的上升子序列中相邻元素不能相等。

阅读更多

动态规划

基本思想

动态规划方法的基本思想是,把求解的问题分成许多阶段或多个子问题,然后按顺序求解各子问题。最后一个子问题就是初始问题的解。

由于动态规划的问题有重叠子问题的特点,为了减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。

动态规划=贪婪策略+递推(降阶)+存储递推结果

阅读更多