1. 路径选择
1.1. House Robber
给一个自然数数组，在不允许相邻取的情况下，求可取的最大和
Input: [1,2,3,1]
Output: 4
取1,3和为4
方法：设定状态dp[n]表示前n项在不能相邻取情况下最大和取法的最大和（结果），要用前面信息表示dp[n]
def rob(self, nums):
n = len(nums);
if n==0: return 0
if n==1: return nums[0]
if n==2: return max(nums[0], nums[1])
dp = [0 for x in range(n)];
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(nums[i]+dp[i-2], dp[i-1])
return dp[-1]
1.2. House Robber ||
在上题的基础上，输入数组是一个环形的（即最后一个和第一个视为相邻）
Input: [2,3,2]
Output: 3
方法：由于第一个和最后一个相邻，那么有如下两种情况：
1. 取第一个的时候，不能取最后一个，相当于把最后一个从数组中去掉
2. 取最后一个的时候，不能取第一个，相当于把第一个从数组中去掉
这样，问题就简化为上一道题的两种输入的叠加形式
def rob(self, nums):
if len(nums) == 0: return 0
if len(nums) == 1: return nums[0]
if len(nums) == 2: return max(nums)
def getRob(start, stop, nums):
# 上一题的解法
n = nums[start: stop + 1]
dp = [0] * len(n)
dp[0], dp[1] = n[0], max(n[0], n[1])
for i in range(2, len(n)):
dp[i] = max(dp[i - 1], dp[i - 2] + n[i])
return dp[-1]
return max(getRob(0, len(nums) - 2, nums), getRob(1, len(nums) - 1, nums))
1.3. House Robber |||
在第10题基础上，变成二叉树形式了，不能取直接相邻的
Input: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
Output: 7
(3 + 3 + 1 = 7)
方法：跟第10题类似，只是加了个dfs来遍历树，下面给出递归法代码（这种树结构不好用迭代法）
class Solution {
public:
int rob(TreeNode* root) {
unordered_map<TreeNode*, int> m;
return dfs(root, m);
}
int dfs(TreeNode *root, unordered_map<TreeNode*, int> &m) {
if (!root) return 0;
if (m.count(root)) return m[root];
int val = 0;
if (root->left) {
val += dfs(root->left->left, m) + dfs(root->left->right, m);
}
if (root->right) {
val += dfs(root->right->left, m) + dfs(root->right->right, m);
}
val = max(val + root->val, dfs(root->left, m) + dfs(root->right, m));
m[root] = val;
return val;
}
};
2. 集合中能重复选择
2.1. Perfect Squares
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
输入一个正整数n, 输出其最少能由几个完全平方数相加组成（完全平方数为1,4,9,16,...）
方法：跟上题类似，设定状态dp[n]为整数n的输出结果，状态转移方程为
int numSquares(int n) {
int *dp = new int[n + 1];
dp[0] = 0;
for (int i=1; i<=n; i++) {
int _min = INT_MAX;
for (int j=1; j*j<=i; j++) {
_min = min(_min, dp[i-j*j]+1);
}
dp[i] = _min;
}
delete[]dp;
return dp[n];
}
2.2. Coin Change
有一些特定面值的货币，如[1,2,5]
现在给定一个价格，如11，最少使用的货币数。
以上输出为3，因为5+5+1=11，如果不能找零输出-1
方法：设定dp[n]为输入为n的结果，状态转移方程为
代码也基本类似，注意这里不能找零-1的处理方法，代码如下
int coinChange(vector<int>& coins, int amount) {
const int int_max = 99999999;
vector<int> dp(amount+1, int_max);
dp[0] = 0;
for(int i=1; i<=amount; i++) {
int _min = int_max;
for(int j=0; j<coins.size(); j++) {
if (i-coins[j]>=0)
_min = min(_min, dp[i-coins[j]]+1);
}
dp[i] = _min;
}
return dp[amount] == int_max ? -1 : dp[amount];
}
2.3. Combination Sum IV
给一个正整数字典，如[1,2,3]，以及一个整数如4
找出整数可被字典元素组成排列组成和的个数，如以上可能组合为
(1, 1, 1, 1)、 (1, 1, 2)、 (1, 2, 1)
(1, 3)、 (2, 1, 1)、 (2, 2)、 (3, 1)
因此输出为7
方法：使用完全背包方法做，代码如下
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned long long> dp(target+1, 0);
dp[0] = 1;
for(int i=1; i<=target; i++) {
for(int j=0; j<nums.size(); j++) {
if (i-nums[j]>=0)
dp[i] += dp[i-nums[j]];
}
}
return dp[target];
}
3. 集合中不可重复选择
3.1. 0-1背包问题
有两个数组w和v，分别记录物品的重量和价值，如果背包重量不能超过m，求一共能达到的最大的价值
方法：设定状态dp[i][c]表示到i号物体截止做选择，重量限制为c的情况下能达到的最大总价值。
现在需要用一个同向（要么都加要么都减）的状态来表示此状态，转换方程如下
const int weight[] = { 2,3,4,5 };
const int value[] = { 3,4,5,6 };
const int n = 4;
const int capacity = 8;
// solve
vector<vector<int>> dp(n, vector<int>(capacity + 1, 0));
for (int i = weight[0]; i <= capacity; i++) dp[0][i] = value[0]; // init
for (int i = 1; i < n; i++) {
for (int c = 0; c <= capacity; c++) {
if (c < weight[i])
dp[i][c] = dp[i - 1][c];
else
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - weight[i]] + value[i]);
}
}
cout << dp[n - 1][capacity] << endl;
// route
int i = n - 1, j = capacity;
while(true) {
if (i == 0) {
if (dp[i][j] != 0) cout << i << endl;
break;
}
if (dp[i][j] == dp[i - 1][j]) i--;
else if (j - weight[i] >= 0 && dp[i][j] == dp[i - 1][j - weight[i]] + value[i]) {
cout << i << endl;
j -= weight[i];
i--;
}
}
3.2. Partition Equal Subset Sum
判断一个正数数组可不可以被拆分为两个子集，使得他们的和相等
Input: [1, 5, 11, 5]
Output: true
可被拆分为 [1, 5, 5] 和 [11].
方法：判断是否成立等价于，判断这个数组中是否有子集的和为总和的一半，
设定状态dp[i][j]表示，数组前i项中是否存在子集的和为j，现在需要用前向的状态表示dp[i][j]，转换关系为
这道题是0-1背包问题的变形，迭代法代码如下
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0), target = sum >> 1;
if (sum & 1) return false;
if (nums.size()==1) return false;
vector<vector<bool>> dp(nums.size(), vector<bool>(target+1));
for(int i=0; i<nums.size(); i++) {
for(int j=0; j<=target; j++) {
dp[i][j] = false;
dp[i][0] = true;
}
}
dp[0][nums[0]] = true;
for(int i=1; i<nums.size(); i++) {
for (int j=nums[i]; j<=target; j++) {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
}
}
return dp[nums.size()-1][target];
}
由于上面方法需要开二维数组比较麻烦，下面对其进行优化
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0), target = sum >> 1;
if (sum & 1) return false;
if (nums.size()==1) return false;
vector<bool> dp(target+1, false);
for(int i=0; i<=target; i++)
dp[i] = i == nums[0];
for(int i=1; i<nums.size(); i++) {
// 注意，此时下面需要从后往前迭代，因为每一个dp[j]的计算都依赖于前面项
for (int j=target; j>=nums[i]; j--) {
dp[j] = dp[j] || dp[j-nums[i]];
}
}
return dp[target];
}