这篇文章上次修改于 891 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
- 给定一个序列
- dp[i] 表示前 i 个元素 a[0], a[1], ..., a[i-1] 的某种性质
- 特征：...前 i 个...最小/方式数/可行性
- 在设计动态规划时，发现需要知道油漆前 i 栋房子的最优策略中，房子 i-1 的颜色。
- 如果只用 dp[i-1] 无法区分。
- 解决方法：记录房子 i-1 的颜色。在房子 i-1 是红/蓝/绿的情况下，油漆前 i 栋房子的最小花费。
- 序列 + 状态
1 房屋染色
这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。
费用通过一个nx3 的矩阵给出，比如cost0表示房屋0染红色的费用，cost1表示房屋1染绿色的费用，依此类推。找到油漆所有房子的最低成本。
输入: [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
解释: 第一个屋子染蓝色，第二个染绿色，第三个染蓝色，最小花费：2 + 5 + 3 = 10.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) {
int n = costs.size();
if (n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(3, INT_MAX));
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
if (i == 0) {
dp[i][j] = costs[i][j];
continue;
}
for (int k = 0; k < 3; k++) {
if (k != j && dp[i - 1][k] + costs[i][j] < dp[i][j]) {
dp[i][j] = dp[i - 1][k] + costs[i][j];
}
}
}
}
return min(dp[n - 1][0], min(dp[n - 1][3], dp[n - 1][4]));
}
};2 房屋染色 II
这里有n个房子在一列直线上，现在我们需要给房屋染色，共有k种颜色。每个房屋染不同的颜色费用也不同，你希望每两个相邻的房屋颜色不同
费用通过一个nxk 的矩阵给出，比如cost0表示房屋0染颜色0的费用，cost1表示房屋1染颜色2的费用。找到油漆所有房子的最低成本。
输入:
costs = [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
说明:
三个屋子分别使用第1,2,1种颜色，总花费是10。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) {
int n = costs.size();
if (n == 0) return 0;
int k = costs[0].size();
if (k == 0) return 0;
vector<vector<int>> dp(n, vector<int>(k, INT_MAX));
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
if (i == 0) {
dp[i][j] = costs[i][j];
continue;
}
for (int p = 0; p < k; p++) {
if (p != j && dp[i-1][p] + costs[i][j] < dp[i][j]) {
dp[i][j] = dp[i-1][p] + costs[i][j];
}
}
}
}
int ans = INT_MAX;
for (int i = 0; i < k; i++) {
if (dp[n-1][i] < ans) {
ans = dp[n-1][i];
}
}
return ans;
}
};优化：记录最小值和次小值
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) {
//
int n = costs.size();
if (n == 0) return 0;
int k = costs[0].size();
if (k == 0) return 0;
vector<vector<int>> dp(n + 1, vector<int>(k, 0));
int j1 = 0, j2 = 0;
int min1 = 0, min2 = 0;
for (int i = 1; i <= n; i++) {
min1 = min2 = INT_MAX;
for (int j = 0; j < k; j++) {
if (dp[i-1][j] < min1) {
min2 = min1;
j2 = j1;
min1 = dp[i-1][j];
j1 = j;
} else if (dp[i-1][j] < min2) {
min2 = dp[i-1][j];
j2 = j;
}
}
for (int j = 0; j < k; j++) {
if (j != j1) {
dp[i][j] = dp[i-1][j1] + costs[i-1][j];
} else {
dp[i][j] = dp[i-1][j2] + costs[i-1][j];
cout << "--" << dp[i][j] << " " << dp[i-1][j2] << " " << costs[i-1][j] << endl;
}
}
}
int ans = INT_MAX;
for (int i = 0; i < k; i++) {
if (dp[n][i] < ans) {
ans = dp[n][i];
}
}
return ans;
}
};3 打劫房屋
假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系统会自动报警。
给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱 。
输入: [3, 8, 4]
输出: 8
解释: 仅仅打劫第二个房子.class Solution {
public:
/**
* @param a: An array of non-negative integers
* @return: The maximum amount of money you can rob tonight
*/
long long houseRobber(vector<int> &a) {
int ans = 0;
int n = a.size();
if (n == 0) return 0;
vector<long long> dp(n + 1, 0);
dp[1] = a[0];
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1];
if (i >= 2 && dp[i] < dp[i-2] + a[i-1]) {
dp[i] = dp[i-2] + a[i-1];
}
}
return dp[n];
}
};4 打劫房屋 II
在上次打劫完一条街道之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子围成了一个圈，这就意味着第一间房子和最后一间房子是挨着的。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系统会自动报警。
给定一个非负整数列表，表示每个房子中存放的钱，算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱。
输入: nums = [3,6,4]
输出: 6枚举：没偷房子 0；没偷房子 n-1。取两种情况的最大值。
class Solution {
public:
/**
* @param nums: An array of non-negative integers.
* @return: The maximum amount of money you can rob tonight
*/
int houseRobber2(vector<int> &nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
vector<int> nums1(nums.begin(), nums.end()-1);
int cnt1 = solve(nums1);
vector<int> nums2(nums.begin()+1, nums.end());
int cnt2 = solve(nums2);
return cnt1 > cnt2 ? cnt1 : cnt2;
}
int solve(vector<int> &a) {
int ans = 0;
int n = a.size();
if (n == 0) return 0;
vector<long long> dp(n + 1, 0);
dp[1] = a[0];
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1];
if (i >= 2 && dp[i] < dp[i-2] + a[i-1]) {
dp[i] = dp[i-2] + a[i-1];
}
}
return dp[n];
}
};5 买卖股票的最佳时机
假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如，一次买卖股票)，设计一个算法来找出最大利润。
输入: [3, 2, 3, 1, 2]
输出: 1
说明：你可以在第三天买入，第四天卖出，利润是 2 - 1 = 1 class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
int n = prices.size();
if (n == 0) return 0;
int mn = prices[0];
int ans = 0;
for (int i = 1; i < n; i++) {
if (prices[i] < mn) {
mn = prices[i];
}
ans = max(ans, prices[i] - mn);
}
return ans;
}
};6 买卖股票的最佳时机 II
给定一个数组 prices 表示一支股票每天的价格.
交易次数不限, 不过你不能同时参与多个交易 (也就是说, 如果你已经持有这支股票, 在再次购买之前, 你必须先卖掉它).
设计一个算法求出最大的利润.
输入: [2, 1, 2, 0, 1]
输出: 2
解释:
1. 在第 2 天以 1 的价格买入, 然后在第 3 天以 2 的价格卖出, 利润 1
2. 在第 4 天以 0 的价格买入, 然后在第 5 天以 1 的价格卖出, 利润 1
总利润 2.class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
if (prices.size() == 0) return 0;
int ans = 0;
for (int i = 0; i < prices.size()-1; i++) {
if (prices[i+1] > prices[i]) {
ans += prices[i+1] - prices[i];
}
}
return ans;
}
};7 买卖股票的最佳时机 III
假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。
输入 : [4,4,6,1,1,4,2,5]
输出 : 6记录阶段：[1]第一次买之前，[2]持有股票，[3]第一次卖之后/第二次买之前，[4]持有股票，[5]第二次卖之后。
如果想买股票，只要知道前一天是什么阶段，就可以知道能不能买。
第 i 天结束后，在阶段 5 的最大获利为 dp[i][12]
- 情况 1：第 i-1 天就在阶段 5
dp[i-1][13] - 情况 2：第 i-1 天在阶段 4
dp[i-1][14] + (p[i] - p[i-1])
第 i 天结束后，阶段 4 的最大获利为 dp[i][15]
- 情况 1：第 i-1 天就在阶段 4
dp[i-1][16] + (p[i-1] - p[i-2]) - 情况 2：第 i-1 天在阶段 3
dp[i-1][17] - 情况 3：第 i-1 天在阶段 2，第 i 天买完了立即买
dp[i-1][18] + (p[i-1] - p[i-2])
第 i 天结束后，处在阶段 j，最大获利：
- 阶段 1，3，5：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + p[i-1] - p[i-2]) - 阶段 2，4：
dp[i][j] = max(dp[i-1][j] + p[i-1] - p[i-2], dp[i-1][j-1], dp[i-1][j-2] + p[i-1] - p[i-2])
class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
int n = prices.size();
if (n == 0) return 0;
vector<vector<int>> dp(n + 1, vector<int>(6));
dp[0][1] = 0;
dp[0][2] = dp[0][3] = dp[0][4] = dp[0][5] = INT_MIN;
for (int i = 1; i <= n; i++) {
// 阶段 1，3，5
for (int j = 1; j <= 5; j += 2) {
dp[i][j] = dp[i-1][j];
if (i > 1 && j > 1 && dp[i-1][j-1] != INT_MIN) {
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + prices[i-1] - prices[i-2]);
}
}
// 阶段 2，4
for (int j = 2; j <= 5; j += 2) {
dp[i][j] = dp[i-1][j-1];
if (i > 1 && dp[i-1][j] != INT_MIN) {
dp[i][j] = max(dp[i][j], dp[i-1][j] + prices[i-1] - prices[i-2]);
}
if (i > 1 && j > 2 && dp[i-1][j-2] != INT_MIN) {
dp[i][j] = max(dp[i][j], dp[i-1][j-2] + prices[i-1] - prices[i-2]);
}
}
}
return max(dp[n][1], max(dp[n][3], dp[n][5]));
}
};8 买卖股票的最佳时机 IV
给定数组 prices, 其中第 i 个元素代表某只股票在第 i 天第价格.
你最多可以完成 k 笔交易. 问最大的利润是多少?
输入: k = 2, prices = [4, 4, 6, 1, 1, 4, 2 ,5]
输出: 6
解释: 以 4 买入, 以 6 卖出. 然后再以 1 买入, 以 5 卖出. 利润为 2 + 4 = 6.如果 k > n/2，相当于任意次买卖，买入价格比下一天低即可买入，与 II 相同。
当 k = 2，与 III 相同。
class Solution {
public:
/**
* @param k: An integer
* @param prices: An integer array
* @return: Maximum profit
*/
int maxProfit(int k, vector<int> &prices) {
int n = prices.size();
if (n == 0) return 0;
if (k > n) {
int ans = 0;
for (int i = 0; i < n - 1; i++) {
if (prices[i + 1] > prices[i]) {
ans += prices[i + 1] - prices[i];
}
}
return ans;
}
vector<vector<int>> dp(n + 1, vector<int>(2 * k + 2));
dp[0][1] = 0;
for (int j = 2; j <= 2 * k + 1; j++) {
dp[0][j] = INT_MIN;
}
for (int i = 1; i <= n; i++) {
// 阶段 1，3，5，...
for (int j = 1; j <= 2 * k + 1; j += 2) {
dp[i][j] = dp[i-1][j];
if (i > 1 && j > 1 && dp[i-1][j-1] != INT_MIN) {
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + prices[i-1] - prices[i-2]);
}
}
// 阶段 2，4，...
for (int j = 2; j <= 2 * k + 1; j += 2) {
dp[i][j] = dp[i-1][j-1];
if (i > 1 && dp[i-1][j] != INT_MIN) {
dp[i][j] = max(dp[i][j], dp[i-1][j] + prices[i-1] - prices[i-2]);
}
if (i > 1 && j > 2 && dp[i-1][j-2] != INT_MIN) {
dp[i][j] = max(dp[i][j], dp[i-1][j-2] + prices[i-1] - prices[i-2]);
}
}
}
int mx = 0;
for (int i = 1; i <= 2 * k + 1; i += 2) {
if (dp[n][i] > mx) {
mx = dp[n][i];
}
}
return mx;
}
};9 买卖股票的最佳时机 V
给出一个股票n天的价格，每天最多只能进行一次交易，可以选择买入一支股票或卖出一支股票或放弃交易，输出能够达到的最大利润值。
给出 `a = [1,2,10,9]`, 返回 `16`
输入:
[1,2,10,9]
输出:
16
解释:
你可以在第一天和第二天买入股票，第三天和第四天卖出
利润：-1-2+10+9 = 16 10 比特位计数
序列 + 位操作型动态规划。
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10class Solution {
public:
vector<int> countBits(int n) {
vector<int> dp(n+1);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i>>1] + (i & 1);
}
return dp;
}
};参考
https://www.bilibili.com/video/BV1nt4y1Y7n7?p=2
https://www.bilibili.com/video/BV1nt4y1Y7n7?p=3
没有评论