House Robber：不能相邻，求能获得的最大值
House Robber II：不能相邻且第一个和最后一个不能同时取，求能获得的最大值
House Robber III：二叉树下的不能相邻，求能获得的最大值
Paint House：用3种颜色，相邻的房屋不能用同一种颜色，求花费最小
Paint House II：用k种颜色，相邻的房屋不能用同一种颜色，求花费最小
Paint Fence：用k种颜色，相邻的可以用同一种颜色，但不能超过连续的2个，求有多少种可能性
198. House Robber
dp[i]表示当前位置获得最大值，偷当前这个位置，就不能偷前一个位置。所以如果偷当前位置，则dp[i] = dp[i-2] + nums[i-1]；如果不偷当前位置，dp[i]就可以前一个相等，即dp[i] = dp[i-1]。
因为要计算i-2，所以初始0位置为0。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.empty())
return ;
vector<int> dp(nums.size() + );
dp[] = ;
dp[] = nums[];
for(int i = ;i <= nums.size();i++){
dp[i] = max(dp[i-] + nums[i-],dp[i-]);
}
return dp[nums.size()];
}
};
https://www.cnblogs.com/lightwindy/p/8648410.html
213. House Robber II
https://www.cnblogs.com/grandyang/p/4518674.html
第一个和最后一个不能同时偷，那就分成两种情况，即偷第一个和偷最后一个分别计算，然后求最大值。
计算的方式类似于House Robber ，不同在于这个题相对于原数组要限制开始和结尾的位置。
如果length为2，会存在开始和结尾相等的情况，这个时候直接返回开始位置的元素就好。所以有如下代码：
if(begin >= end)
return nums[begin];
其实也可以单独写个n == 2的情况进行判断。
length为1理论上也可以用刚才这个进行处理，但是因为begin是从1开始的，会造成越界，所以对length为1进行了单独判断。
rob_core的写法与House Robber 类似，需要注意dp的索引是根据索引来的，相对应的nums的索引也必须进行变化。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.empty())
return ;
if(nums.size() == )
return nums[];
return max(rob_core(nums,,nums.size()-),rob_core(nums,,nums.size()-));
}
int rob_core(vector<int>& nums,int begin,int end){
if(begin >= end)
return nums[begin];
int length = end - begin + ;
vector<int> dp(length + );
dp[] = ;
dp[] = nums[begin];
for(int i = ;i <= length;i++){
dp[i] = max(dp[i-] + nums[begin + i - ],dp[i-]);
}
return dp[length];
}
};
337. House Robber III
https://www.cnblogs.com/grandyang/p/5275096.html
修改返回值变成长度为2的vector，0位置代表不使用当前的元素，1位置代表使用当前的元素。
如果使用就是之前left、right不使用加上当前位置的数值。如果不使用，那就是需要获得left、right的最大值，这个最大值可能是left节点使用、也可能是不使用，right同理。(其实这样做的原因是隐含条件所有数值是大于0的，所以必须加上左右的值，只是选择到底加左右的什么值)
注意：left、right的最大值不一定是使用，所以找各自的最大值相加就好。并且left、right使不使用的选择，对当前节点都没有影响，因为当前节点反正都是不使用，所以只需要找各自的最大值。
class Solution {
public:
int rob(TreeNode* root) {
vector<int> result = robCore(root);
return max(result[],result[]);
}
vector<int> robCore(TreeNode* root){
if(root == NULL)
return vector<int> (,);
vector<int> left = robCore(root->left);
vector<int> right = robCore(root->right);
vector<int> result();
result[] = max(left[],left[]) + max(right[],right[]);
result[] = left[] + right[] + root->val;
return result;
}
};
256. Paint House
这个题与House Robber不同在于，不仅对相邻的关系进行了约束，还需要求最小值。
dp[i][j]表示使用j这种颜色当前位置的最小值，由于相邻颜色不能相同，所以更新只能来自于前一个位置另外两种颜色的最小值。
最后再在最后一个位置求三种颜色的最小值就好。
class Solution {
public:
/**
* @param costs: n x 3 cost matrix
* @return: An integer, the minimum cost to paint all houses
*/
int minCost(vector<vector<int>> &costs) {
// write your code here
if(costs.empty())
return ;
if(costs[].empty())
return ;
vector<vector<int>> dp(costs.size() + ,vector<int>(,));
for(int i = ;i <= costs.size();i++){
dp[i][] = min(dp[i-][],dp[i-][]) + costs[i-][];
dp[i][] = min(dp[i-][],dp[i-][]) + costs[i-][];
dp[i][] = min(dp[i-][],dp[i-][]) + costs[i-][];
}
int res = min(dp[costs.size()][],min(dp[costs.size()][],dp[costs.size()][]));
return res;
}
};
265. Paint House II
https://www.cnblogs.com/grandyang/p/5322870.html
这个题也可以使用Paint House的方法，但会超时。
当前位置的最小值来自于前一个位置的最小值+当前位置的cost，但是由于不能相同颜色不能相邻，所以如果计算到相同颜色时，就使用第二小的花费进行更新。
min1、min2、last1、last2都是针对的行，min1、min2针对是当前行的最小和第二小，last1、last2针对的是上一行的最小和第二小。
last2 == -1、last1 == -1是在第一行进行更新时做的处理，因为第一行其实没有前一行。
因为每一行都需要计算所有列的最小值，并且min1 、min2必须每行都重新初始化，min1 == -1和min2 == -1是针对第一、第二列的更新。
class Solution {
public:
/**
* @param costs: n x k cost matrix
* @return: an integer, the minimum cost to paint all houses
*/
int minCostII(vector<vector<int>> &costs) {
// write your code here
if(costs.empty())
return ;
if(costs[].empty())
return ;
vector<vector<int>> dp = costs;
int min1 = -,min2 = -;
for(int i = ;i < costs.size();i++){
int last1 = min1,last2 = min2;
min1 = - ,min2 = -;
for(int j = ;j < costs[].size();j++){
if(j == last1)
dp[i][j] += last2 == - ? : dp[i-][last2];
else
dp[i][j] += last1 == - ? : dp[i-][last1];
if(min1 == - || dp[i][j] < dp[i][min1]){
min2 = min1;
min1 = j;
}
else if(min2 == - || dp[i][j] < dp[i][min2])
min2 = j;
}
}
return dp[costs.size() - ][min1];
}
};
自己写的另一种写法：
没有将dp一开始初始化为costs。
如果不加括号，就会报错
class Solution {
public:
/**
* @param costs: n x k cost matrix
* @return: an integer, the minimum cost to paint all houses
*/
int minCostII(vector<vector<int>> &costs) {
// write your code here
int m = costs.size();
if(m == )
return ;
int n = costs[].size();
if(n == )
return ;
vector<vector<int>> dp(m,vector<int>(n));
int cur1 = -,cur2 = -;
for(int i = ;i < m;i++){
int last1 = cur1,last2 = cur2;
cur1 = -,cur2 = -;
for(int j = ;j < n;j++){
if(j != last1)
dp[i][j] = costs[i][j] + (last1 == - ? : dp[i-][last1]);
else if(j == last1)
dp[i][j] = costs[i][j] + (last2 == - ? : dp[i-][last2]);
if(cur1 == - || dp[i][j] < dp[i][cur1]){
cur2 = cur1;
cur1 = j;
}
else if(cur2 == - || dp[i][j] < dp[i][cur2])
cur2 = j;
}
}
return dp[m-][cur1];
}
};
276. Paint Fence
这个题算是斐波那契数列和House Robber的结合。
dp[i]表示当前位置所有的方式。当前位置可以选择与前两个位置不同颜色，也可以选择和前一个位置不同颜色，与前两个位置不同颜色就是dp[i-2] * (k-1)，与前一个位置不同颜色就是dp[i-1] * (k-1)。与前一个位置不同颜色保证一定不会出现相邻的情况，与前两个位置不同颜色也保证了相邻的颜色不会超过2。
注意：k为1时，n=1、n=2的个数都是1，要注意这个corner case
class Solution {
public:
/**
* @param n: non-negative integer, n posts
* @param k: non-negative integer, k colors
* @return: an integer, the total number of ways
*/
int numWays(int n, int k) {
// write your code here
if(k <= && n > )
return ;
if(n <= )
return ;
vector<int> dp(n);
dp[] = k;
dp[] = k*k;
for(int i = ;i < n;i++)
dp[i] = dp[i-] * (k-) + dp[i-] * (k-);
return dp[n-];
}
};
上面这个代码n == 1的情况没考虑
class Solution {
public:
/**
* @param n: non-negative integer, n posts
* @param k: non-negative integer, k colors
* @return: an integer, the total number of ways
*/
int numWays(int n, int k) {
// write your code here
if(k == && n > )
return ;
if(n == )
return ;
if(n == )
return k;
vector<int> dp(n);
dp[] = k;
dp[] = k*k;
for(int i = ;i < n;i++)
dp[i] = dp[i-]*(k-) + dp[i-]*(k-);
return dp[n-];
}
};