Derolol Blog

0/1 背包

准备多种大小的背包，当物品体积小于背包时，可尝试比较当前已放置物品价值，与当前物品价值和更小体积背包放置物品价值之和，取更大值

leetcode416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (auto n : nums) sum += n;
    // 若累加值为奇数，则不可能存在这样的两个子集
    if (sum % 2 != 0) return false;
    sum >>= 1;
    int n = nums.size();
    // 判断大小为sum的背包，是否能恰好装入价值为sum的物品
    // 其中，各个物品的体积和价值均为nums[i]
    vector<int> maxPack(sum + 1);
    for (auto n : nums) {
        if (n > sum) return false;
        for (int i = sum; i >= n; i --) {
            maxPack[i] = max(maxPack[i], maxPack[i - n] + n);
        }
    }
    return maxPack[sum] == sum;
}

一维动态规划

leetcode139 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

bool wordBreak(string s, vector<string>& wordDict) {
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (int i = 1, len = s.size(); i <= len; i ++) {
        bool flag = false;
        for (string word : wordDict) {
            if (i < word.size()) continue;
            int start = i - word.size();
            if (dp[start] && s.substr(start, word.size()) == word) {
                flag = true;
                break;
            }
        }
        dp[i] = flag;
    }
    return dp[s.size()];
}

牛客 2021360 春招编程题(第一批) 火星人的宝藏

X 星人发现了一个藏宝图，在藏宝图中标注了 N 个宝库的位置。这 N 个宝库连成了一条直线，每个宝库都有若干枚金币。 X 星人决定乘坐热气球去收集金币，热气球每次最多只能飞行 M 千米（假设热气球在飞行过程中并不会发生故障）此外，由于设计上的缺陷，热气球最多只能启动 K 次。 X 星人带着热气球来到了第 1 个宝库（达到第 1 个宝库时热气球尚未启动），收集完第 1 个宝库的金币后将启动热气球前往下一个宝库。如果他决定收集某一个宝库的金币，必须停下热气球，收集完之后再重新启动热气球。当然，X 星人每到一个宝库是一定会拿走这个宝库所有金币的。 已知每一个宝库距离第 1 个宝库的距离（单位：千米）和宝库的金币数量。 请问 X 星人最多可以收集到多少枚金币？

输入描述： 单组输入。

第 1 行输入三个正整数 N、M 和 K，分别表示宝库的数量、热气球每次最多能够飞行的距离（千米）和热气球最多可以启动的次数，三个正整数均不超过 100，相邻两个正整数之间用空格隔开。

接下来 N 行每行包含两个整数，分别表示第 1 个宝库到某一个宝库的距离（千米）和这个宝库的金币枚数。（因为初始位置为第 1 个宝库，因此第 1 个宝库所对应行的第 1 个值为 0。）

输入保证所有的宝库按照到第 1 个宝库的距离从近到远排列，初始位置为第 1 个宝库。

输出描述： 输出一个正整数，表示最多可以收集的金币数。

示例 1 输入例子： 5 10 2 0 5 8 6 10 8 18 12 22 15 输出例子： 25 例子说明： X 星人启动热气球两次，分别收集第 1 个、第 3 个和第 4 个宝库的金币，一共可以得到的金币总数为 5+8+12=25 枚。

题解

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M, K;
    while (cin >> N >> M >> K) { // 注意 while 处理多个 case
        vector<vector<int>> ship(N, vector<int>(2, 0));
        vector<vector<int>> dp(N, vector<int>(K + 1, 0));
        int k, v;
        for (int i = 0; i < N; i ++) {
            cin >> k >> v;
            ship[i][0] = k;
            ship[i][1] = v;
            if (i > 0 && k <= M) {
                dp[i][1] = max(dp[i - 1][1], v);
            }
        }
        if (N - 1 <= K) {
            long long ret = 0;
            for (int i = 1; i < N; i ++) {
                if (ship[i][0] - ship[i - 1][0] > M) break;
                ret += ship[i][1];
                // cout << ret << endl;
            }
            cout << ret + ship[0][1];
            return 0;
        }
        for (int k = 2; k <= K; k ++) {
            for (int n = k; n < N; n ++) {
                int nn = n - 1;
                int maxV = 0;
                while (nn >= k - 1) {
                    if (dp[nn][k - 1] == 0) {
                        nn --;
                        continue;
                    }
                    if (ship[n][0] - ship[nn][0] > M) break;
                    maxV = max(maxV, dp[nn][k - 1] + ship[n][1]);
                    nn --;
                }
                dp[n][k] = maxV;
                // if (k == K) cout << "n: " << n << " k: " << k << " dp:" << dp[n][k] << endl;
            }
        }
        int ret = 0;
        for (int i = K; i < N; i ++) {
            ret = max(ret, dp[i][K]);
        }
        cout << ret + ship[0][1];
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

leetcode221 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1])

---

leetcode873 最长的斐波那契子序列的长度

思路

• 状态定义

  其中表示以位置 i 和 j 结尾的子序列

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        if (n < 3) return 0;
        if (n == 3) {
            if (arr[0] + arr[1] == arr[2]) return 3;
            return 0;
        }
        int maxLen = 0;
        vector<vector<int>> m(n, vector<int>(n, 0));
        unordered_map<int, int> diff;
        for (int i = 1; i < n - 1; i ++) {
            diff[arr[i - 1]] = i - 1;
            for (int j = i + 1; j < n; j ++) {
                int interval = arr[j] - arr[i];
                if (diff.count(interval)) {
                    m[i][j] = m[diff[interval]][i] + 1;
                    maxLen = max(maxLen, m[i][j]);
                }
            }
        }
        return maxLen > 0 ? maxLen + 2 : 0;
    }
};

最大子数组和

leetcode918 环形子数组的最大和

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

思路

通常对于环形数组的最大子数组和有两种情形，一种是不需要首尾相连的子数组，另一种则是需要连接开头的子数组 对于子数组 1，其求解方式与传统求解方法一样； 对于子数组 2，可以通过逆向思维求解，由于子数组 2 为最大子数组，所以数组的和减去子数组 2 的和，得到的是最小子数组 3，子数组 3 的首位是不相连的

int maxSubarraySumCircular(vector<int>& nums) {
    int maxSum = nums[0], minSum = nums[0];
    int preMaxSum = nums[0], preMinSum = nums[0];
    int sum = nums[0];
    for (int i = 1, len = nums.size(); i < len; i ++) {
        // 对比局部最大与当前值
        preMaxSum = max(preMaxSum + nums[i], nums[i]);
        // 对比最大值与局部最大
        maxSum = max(preMaxSum, maxSum);
        // 对比局部最小与当前值
        preMinSum = min(preMinSum + nums[i], nums[i]);
        // 对比最小值与局部最小
        minSum = min(preMinSum, minSum);
        // 数组累加和
        sum += nums[i];
    }
    // 若此时最大值为负值，即所有值为负值，则不存在两个子数组
    if (maxSum < 0) return maxSum;
    // 对比两个子数组
    return max(maxSum, sum - minSum);
}

逆向动态规划

leetcode174. 地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。 为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。 返回确保骑士能够拯救到公主所需的最低初始健康点数。 注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

思路

对于任意位置，其起始健康点数取决于后续经过的房间，所以尝试使用逆向 DP 解题 对比理解，若问题为到达终点的最大健康点数，对于任意位置，其最大健康点数只与已经经过的房间有关，可以使用正向 DP 解题 根据观察发现，当后续房间值为非负值时，对起始健康点数无影响；而当后续房间值为负值时，起始健康点数应为负值的相反数。由此可得到状态转移方程为： 其中，操作用于获得所需健康点数更小的后续房间值，操作则将正值置，保留负值 为了实现原地算法，将所需健康点数累加到当前位置，若累加后值为正，则代表加上当前房间值后，后续的路径勇士都有足够的健康点数，否则代表需要更大的健康点数 另外，由于勇士只有在健康点数为时才能存活，所以对于负值为的房间，需要保证起始健康点数为

时间复杂度: 空间复杂度:

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int m = dungeon.size(), n = dungeon[0].size();
    for (int i = m - 1; i >= 0; i --) {
        int j = (i == m - 1) ? n - 2 : n - 1;
        for (; j >= 0; j --) {
            int right = (j + 1 == n) ? dungeon[i + 1][j] : dungeon[i][j + 1];
            int bottom = (i + 1 == m) ? dungeon[i][j + 1] : dungeon[i + 1][j];
            dungeon[i][j] += min(max(right, bottom), 0);
        }
    }
    return dungeon[0][0] > 0 ? 1 : (- 1 * dungeon[0][0]) + 1;
}

leetcode213 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

分类讨论动态规划

可考虑两种可能的情况，一种为小偷偷了第一家，最后一家就不能偷；第二种情况为小偷没有偷第一家