一、0/1背包问题
参考博客，主要注意以下几个方面：
1 背包问题要素： 背包容积、物品价值、物品体积
2 dp含义，dp[j]表示为j体积下，最大的物品价值。
3 遍历顺序，如果是二维写法，可以不关心顺序，但是如果是一维写法，需要关心遍历顺序
4 初始化值，需要根据dp定义含义做初始化定义。
二、416 分割等和子集
主要是怎么思考，去和01背包问题联系起来：
首先，dp[j]代表什么？容量为j的背包，所背的物品价值最大可以为dp[j]。dp[j]表示背包总容量（所能装的总重量）是j，放进物品后背包的最大重量为dp[j]。换句话说，在此题目中，背包容积和价值都是num[x]。所以状态公式为：
dp[j] = max(dp[j] , dp[j - nums[i]] + nums[i])
考虑初始化情况，当dp[0]应该为0，总容量为0，能背的最大的重量也为0
遍历顺序应该先遍历物品 再遍历体积。
//sum
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
int getSum(int* nums, int numsSize)
{
int sum = 0;
for(int i = 0; i < numsSize; i++)
{
sum += nums[i];
}
return sum;
}
bool canPartition(int* nums, int numsSize) {
int sum = 0;
sum = getSum(nums, numsSize);
if(sum % 2)
{
return false;
}
//初始化dp
int target = sum/2;
int* dp = (int*)calloc((target + 1), sizeof(int));
for(int i = 0 ; i < numsSize; i++)
{
for(int j = target; j >= nums[i]; j--)
{
dp[j] = MAX(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[target] == target;
}另外，二维数组的写法如下：
//sum
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
int getSum(int* nums, int numsSize)
{
int sum = 0;
for(int i = 0; i < numsSize; i++)
{
sum += nums[i];
}
return sum;
}
bool canPartition(int* nums, int numsSize) {
int sum = 0;
sum = getSum(nums, numsSize);
if(sum % 2)
{
return false;
}
//初始化dp
int target = sum/2;
int** dp = (int**)malloc(sizeof(int*) * (numsSize+1));
for(int i = 0; i <= numsSize; i++)
{
dp[i] = (int*)calloc(target + 1, sizeof(int));
}
for(int j = nums[0]; j <= target; ++j) {
dp[0][j] = nums[0];
}
for(int i = 1; i < numsSize; i++)
{
for(int j = 1; j <= target; j++)
{
//状态转移公式
// 若当前背包重量j小于nums[i]，则其值等于只考虑0到i-1物品时的值
if(j < nums[i])
dp[i][j] = dp[i - 1][j];
// 否则，背包重量等于在背包中放入num[i]/不放入nums[i]的较大值
else
dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
}
}
if(target == dp[numsSize - 1][target])
{
return true;
}
return false;
}三、1049 最后一块石头重量II
一开始阅读题目，根本联系不到01背包，但是仔细分析，题目可以转化为求2堆相近的石头，这样大堆减小堆石头，得到的值应该就是最小值。但是怎么求其中某一堆石头呢？
结合分割等和子集，找到一个target，利用01背包，就可以找到最大的dp，即找到最大的石头堆。怎么获取target，一个整体分成两部分，那么和对半分，就是需要石头堆的最大值。
int getSum(int* stones, int stonesSize)
{
int sum = 0;
for(int i = 0; i < stonesSize; i++)
{
sum += stones[i];
}
return sum;
}
#define MAX(a, b) (a) > (b)? (a) : (b)
int lastStoneWeightII(int* stones, int stonesSize) {
//把问题拆分成：划分成两块相近的石头堆，就可以使用0、1背包
int dp[15001] = {0};//根据题目限制
int max_stone = getSum(stones, stonesSize);
int target = (getSum(stones, stonesSize))/2;
//目标就是找到sum的一半下dp最大值。
for(int i = 0; i < stonesSize; i++)
{
for(int j = target; j >= stones[i]; j--)
{
dp[j] = MAX(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return max_stone - dp[target] * 2;
}四、494 目标和
题目主要点还是如何转化：本题要如何使表达式结果为target，既然为target，那么就一定有 left组合 - right组合 = target。left + right = sum，而sum是固定的。right = sum - left。
left - (sum - left) = target
推导出 left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。
left可以理解为正数之和， right就是负数之和，因为题目描述 + -两个运算符，只可能这两个情况。
题目转化成01背包问题。
还需要注意点，就是前面的背包问题是求最大值。但是这里求的是多少种可能组合。所以dp含义是有区别的。
int findTargetSumWays(int* nums, int numsSize, int target) {
//题目是说找多少种方案
if(numsSize <= 0)
{
return 0;
}
int sum = 0;
for(int i = 0; i < numsSize; i++)
{
sum += nums[i];
}
if(abs(target) > sum)
{
return 0;
}
if((sum + target) % 2)
{
return 0;
}
//初始化dp
int bagsize = (sum + target)/2;//正数
int* dp = (int*)calloc(bagsize + 1, sizeof(int));
dp[0] = 1;
for(int i = 0; i < numsSize; i++)
{
for(int j = bagsize; j >= nums[i]; j--)
{
dp[j] += dp[j - nums[i]];
}
}
return dp[bagsize];
}五、474 一和零
这里关注点是0和1是两个维度（m 和 n相当于是一个背包，两个维度的背包）。dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。递推公式为：
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
#define MAX(a, b) (a) > (b)? (a) : (b)
int findMaxForm(char** strs, int strsSize, int m, int n) {
int** dp = (int**)malloc(sizeof(int*) * (m + 1));
for(int i = 0; i <= m; i++)
{
dp[i] = calloc(n + 1, sizeof(int));
}
//初始化成0
for(int i = 0; i < strsSize; i++)
{
int zeroNum = 0;
int oneNum = 0;
for(int j = 0; j < strlen(strs[i]); j++)
{
if(strs[i][j] == '0')
{
zeroNum++;
}
else
{
oneNum++;
}
}
for(int p = m; p >= zeroNum; p--)
{
for(int q = n; q >= oneNum; q--)
{
dp[p][q] = MAX(dp[p][q], dp[p - zeroNum][q - oneNum] + 1);
}
}
}
return dp[m][n];
}
