===
Index
扔鸡蛋
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
解答
- 如果你从某一层楼扔下鸡蛋，它没有碎，则这个鸡蛋你可以继续用
- 如果这个鸡蛋摔碎了，则你可以用来测试的鸡蛋减少一个
- 所有鸡蛋的质量相同（都会在同一楼层以上摔碎）
- 如果在第i层扔下的时候摔碎了，则对不小于i层的楼层都会摔碎
- 如果在第i层扔下的时候没摔碎，则对不大于i层的楼层都不会摔碎
- 从第1层扔下，鸡蛋不一定完好，从第36层扔下，鸡蛋也不一定会摔碎。
考虑n个鸡蛋k层楼，当我们从楼层x扔下鸡蛋时，有两种情况，1：鸡蛋破，2：鸡蛋不破
- 鸡蛋破，只需用剩下的鸡蛋测试x层以下的楼层，问题化简为x-1层和n-1个鸡蛋
- 如果没有破，我们只需检查比x高的楼层，所以问题化简为k-x和n个鸡蛋
superEggDrop(int K, int N) {
vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));
for (int i = 0; i <= N; i++) dp[i][1] = i;
for (int i = 1; i <= N; i++) {
for (int k = 2; k <= K; k++) {
int res = INT_MAX;
for (int j = 1; j <= i; j++) {
res = min(res , max(dp[j-1][k-1], dp[i-j][k]) + 1);
}
dp[i][k] = res;
}
}
return dp[N][K];
}
数学方法
如果我们可以做 t 次操作，而且有 k 个鸡蛋，那么我们能找到答案的最高的 n 是多少？我们设 f(t,k) 为在上述条件下的 n。如果我们求出了所有的 f(t,k)，那么只需要找出最小的满足 f(t,k) ≥ n 的 t。
*
* 没碎 f(t-1, k)
* 1 f(t,k) = f(t-1,k)+f(t-1,k-1)+1;
*
* 碎了 f(t-1, k-1)
*
int superEggDrop(int k, int n) {
if (n == 1) return 1;
vector<vector<int>> f(n + 1, vector<int>(k + 1));
for (int i = 1; i <= k; ++i) {
f[1][i] = 1;
}
int ans = -1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j];
}
if (f[i][k] >= n) {
ans = i;
break;
}
}
return ans;
}
int superEggDrop(int k, int n){
vector<int> f(k + 1);
int cnt = 0;
while (f[k] < n) {
++cnt;
for (int i = k; i > 0; --i)
f[i] += f[i - 1] + 1;
}
return cnt;
}
俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
分析
我们考虑固定一个维度，再在另一个维度上进行选择。例如，我们固定 w 维度，那么我们将数组 envelopes 中的所有信封按照 w 升序排序。这样一来，我们只要按照信封在数组中的出现顺序依次进行选取，就一定保证满足：
w0 <= w1 <= ... <= wk-1
在 w 值互不相同的前提下，小于等于 ≤ 和小于 < 是等价的，那么我们在排序后，就可以完全忽略 w 维度，只需要考虑 h 维度了。此时，我们需要解决的问题即为：
给定一个序列，我们需要找到一个最长的子序列，使得这个子序列中的元素严格单调递增，即上面要求的：
h_0 < h_1 < ... < h_{k-1}
这个问题就是经典的「最长严格递增子序列」问题了
int maxEnvelopes(vector<vector<int>>& e) {
if(e.empty()) return 0;
sort(e.begin(), e.end());
vector<int> dp(e.size(), 1);
for (int i = 0; i < e.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (e[j][0] < e[i][0] && e[j][1] < e[i][1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
石子合并
有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。
int mergeStones(vector<int>& stones, int K) {
int N = (int)stones.size();
if((N - 1) % (K - 1)) return -1;
vector<int> sum(N + 1, 0);
for(int i = 0; i < N; i++) sum[i + 1] = sum[i] + stones[i];
vector<vector<int> > dp(N + 1, vector<int>(N, 0));
for(int l = K; l <= N; l++)
for(int i = 0; i + l <= N; i++)
{
dp[l][i] = 10000;
for(int k = 1; k < l; k += K - 1)
dp[l][i] = min(dp[l][i], dp[k][i] + dp[l - k][i + k]);
if((l - 1) % (K - 1) == 0) dp[l][i] += sum[i + l] - sum[i];
}
return dp[N][0];
}
每次只能合并相邻两堆。
#include <iostream>
using namespace std;
const int N = 307;
int a[N], s[N];
int f[N][N];
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
s[i] += s[i - 1] + a[i];
}
// 区间 DP 枚举套路：长度+左端点
for (int len = 1; len < n; len ++) { // len表示i和j堆下标的差值
for (int i = 1; i + len <= n; i ++) {
int j = i + len; // 自动得到右端点
f[i][j] = 1e8;
for (int k = i; k <= j - 1; k ++) { // 必须满足k + 1 <= j
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}
零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
int coinChange(vector<int>& coins, int n) {
vector<int> dp(n + 1, INT_MAX/2);
dp[0] = 0;
for (int i = 0; i <= n; ++i) {
for (auto x : coins)
if (i >= x)
dp[i] = min(dp[i], dp[i - x] + 1);
}
return dp[n] == INT_MAX / 2 ? -1 : dp[n];
}
零钱兑换2
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
int change(int amount, vector<int>& coins) {
int dp[amount+1];
memset(dp,0,sizeof(dp));
dp[0]=1;
for (auto coin : coins) {
for (int i = coin; i <= amount; ++i)
dp[i] += dp[i - coin];
}
return dp[amount];
}
目标和
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
int findTargetSumWays(vector<int>& nums, int S) {
long long sum = accumulate(nums.begin(), nums.end(), 0);
if ((sum + S) & 0x1 || S > sum || S < -sum) return 0;
int p = S + ((sum - S) >> 1), n = nums.size();
int dp[p + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = p; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[p];
}
分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200
分析
- 如果数组和为奇数，直接返回false，否则转化为01背包问题
- 从数组中选取一部分数，能否使得背包容量恰好为s / 2。
bool canPartition(vector<int>& nums) {
int s = 0;
for (auto x : nums) s += x;
if (s & 1) return false;
vector<int> dp(s / 2 + 1);
dp[0] = 1;
for (auto x : nums) {
for (int i = dp.size() - 1; i >= x; --i) {
if (dp[i - x]) dp[i] = 1;
}
}
return dp.back() == 1;
}
