先来看一个例题

• （leetcode-416）给你一个n个元素的数组A，如果该数组可以分成两个和相等的子数组，返回true，否则返回false，数组长度不超过200，数组元素不超过100

整个数组A的和我们是能求出来的，由于我们需要分成两个和相等的子数组，那么两个子数组的和我们也能算出来。题目可以转换成：

• 给你一个n个元素的数组A，能否从中取出若干个元素，使得这些元素的和为sum/2

我们使用数组B={b1,b2,b3,…,}，里面每个元素的取值范围是0或者1，表示A{i}是否被选择，1表示选择，0表示未被选择，这样我们就可以用一个数学式子来表示

规划问题

从数学上来说，这一类问题为了达到某一个目标（函数值最小，函数值最大，或者函数值等于某个值），我们需要确定n个变量的值，这一个过程叫规划

常见的规划问题有，线性规划，整数规划，01规划等等，那些神经网络本质上也属于规划问题

动态规划

动态规划首先是个整数规划。整数规划是np完全问题，动态规划就是利用一些特殊的限定条件，使得将问题转换成多项式复杂度。

也就是说，动态规划描述了一种解决特殊规划问题的办法。动态，顾名思义，就是增量计算。假设我们已经规划好n个变量，如果再加上一个变量，我们不再需要重新规划前面那n个变量，只需要规划这第n+1个变量，这种方式叫动态规划

动态规划有三个条件

• 合适的中间状态
• 增量计算中，中间状态的更新方式，也称为状态转移方程
• 中间状态必须远小于n个变量的状态空间

第三个条件是关键，如果没有这个条件，那么搜索空间并没有变化，使用动态规划跟不使用动态规划没有性能上的提升，也就没有意义了

动态规划的解题思路

前面那个例子，如果不用动态规划的思想，我们需要枚举所有的B数组的可能性，也就是2^n种可能性

由于题目限定数据范围，数组长度不超过200，数组元素不超过100，那么说明元素和不超过20000。我们引入中间状态C={C0,C1,…C10000}，每个元素为0或1，第i个元素表示前面p个元素是否有存在和为i的子集。那么我们把状态空间降到了最高10000个，每次加入一个元素，只需要更新这最高10000个状态即可

假设这个题目没有限定数据范围。数组元素可以任意大，那么我们的中间状态空间最高可达2^n种可能，那么我们也没必要使用这种方式来解题

为什么2^n种可能性会降到只剩下10000种可能呢？因为中间有很多可能性产生的状态一致，比如集合{1,2,3,4,5}中，{2,3,4}和{1,3,5}产生的状态都是9，这些状态既然一致，并且如何得出这些状态是无关紧要的，因为如果这个集合再加入一个数，我们只需要拿状态值为9来计算得到下一个状态即可，并不需要理会是从{2,3,4}还是{1,3,5}得到的状态值，这种就大量的压缩了搜索状态空间。

例题的解答

• 状态：state[i]表示是否存在和为i的子集，0<=i<=10000
• 状态更新（当计算到第k个数时）：

$state[i] = state[i] || state[i-nums[k]]$

这里表示两种情况，加入第k个数，跟不加入第k个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool flag[10010];
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int i = 0;i < nums.size();i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) {
            return false;
        }
        memset(flag, false, sizeof(flag));
        flag[0] = true;
        for (int i = 0;i < nums.size();i++) {
            for (int j = sum / 2;j >= nums[i];j--) {
                flag[j] = flag[j] || flag[j - nums[i]];
            }
        }
        return flag[sum / 2];
    }
};