思路：本题可以看成是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的一个子序列。

最长递增子序列 的进阶版本

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

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

基本思想

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

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

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

斐波那契数列

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

输入：
4
返回值：
3

说明：
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。