Celery's Blog

0%

LeetCode-Day37

发表于 Valine：

LeetCode-Day37——还在动态规划

368. 最大整除子集

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

示例 1:

1
2
3
4
5
6
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
示例 2:

输入: [1,2,4,8]
输出: [1,2,4,8]

思路：

其实也没啥思路，就是先进行排序，然后用i顺序遍历, 用j 在[0, i]区间内遍历，查找能否加入当前满足的最大的整除子集，记录下满足的点的下标。

然后逆向查找，返回res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
    int n = nums.size();
    if(n < 2) {
        return nums;
    }
    vector<int> dp(n, 1);
    vector<int> index(n, -1);
    vector<int> res;
    sort(nums.begin(), nums.end());
    int maxStart = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < i;j++) {
            if(nums[i] % nums[j] == 0) {
                if(dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    index[i] = j;
                }
            }
        }
        maxStart = dp[maxStart] > dp[i] ? maxStart : i;
    }
    while(maxStart > -1) {
        res.push_back(nums[maxStart]);
        maxStart = index[maxStart];
    }
    return res;
    }
};

375. 猜数字大小II

依然DP

算法：

以i为第一次尝试找到最小开销的过程可以被分解为找左右区间内最小开销的子问题。对于每个区间，我们重复问题拆分的过程，得到更多子问题，这启发我们可以用DP解决这个问题。

我们需要使用一个dp数组，其中dp(i, j)代表在(i, j)中最坏情况下的最小开销。现在我们只需要考虑如何求出这个dp数组。如果区间只剩下一个数k,那么猜中的代价永远为0，因为我们区间里只剩下一个数字，也就是说，所有的dp(k, k)都初始化为0。然后，对于长度为2的区间，我们需要所有长度为1的区间的结果。由此我们可以看出，为了求出长度为len区间的解。因此我们按照区间长度从短到长求出dp数组。

现在，我们应该按照什么办法来求出dp矩阵呢？对于每个dp(i, j)，当前长度为len = j - i + 1，我们一次挑选每个数字作为第一次尝试的答案。

cost(i, j) = pivot + max(cost(i, pivot - 1), cost(pivot + 1, n))

但是在计算开销的时候，我们有一个便利之处，就是我们已经知道了小于len长度的dp数组的所有答案。因此dp方程变成了

dp(i,j)=minpivots(i,j)[pivot+max(dp[i,pivot−1],dp[pivot+1,n])]dp(i, j) = min_{pivots(i, j)}[pivot + max(dp[i, pivot - 1], dp[pivot + 1, n])]

其中minpivots(i,j)min_{pivots(i, j)}表示将(i, j)中的每个数作为第一个尝试的数字

上Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int getMoney(int n) {
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    // 遍历长度，分别枚举长度从2 - n的分段，因为长度为1的花销为0
    for(int len = 2;len <= n;len++) {
        // 遍历start的位置，从start开始，取长度为len，所以start必须要小于等于(n - len + 1)
        for(int start = 1;start <= n - len + 1;start++) {
            int minres = INT_MAX;
            // 遍历(start, start + len)的区间，寻找最小代价
            for(int piv = start; piv < start + len - 1;piv++) {
                int res = piv + max(dp[start][piv - 1], dp[piv + 1][start + len - 1]);
                minres = min(res, minres);
            }
            dp[start][start + len - 1] = minres;
        }
    }
    return dp[1][n];
}

403. 青蛙过河

一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。

给定石子的位置列表（用单元格序号升序表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。 开始时， 青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

请注意：

石子的数量 ≥ 2 且 < 1100；
每一个石子的位置序号都是一个非负整数，且其 < 231；
第一个石子的位置永远是0。
示例 1:

1
2
3
4
5
6
7
8
9
10
[0,1,3,5,6,8,12,17]
总共有8个石子。
第一个石子处于序号为0的单元格的位置, 第二个石子处于序号为1的单元格的位置,
第三个石子在序号为3的单元格的位置， 以此定义整个数组...
最后一个石子处于序号为17的单元格的位置。

返回 true。即青蛙可以成功过河，按照如下方案跳跃： 
跳1个单位到第2块石子, 然后跳2个单位到第3块石子, 接着 
跳2个单位到第4块石子, 然后跳3个单位到第6块石子, 
跳4个单位到第7块石子, 最后，跳5个单位到第8个石子（即最后一块石子）。

示例 2:

1
2
3
4
[0,1,2,3,4,8,9,11]

返回 false。青蛙没有办法过河。 
这是因为第5和第6个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。

有点难… 嗯…看看代码注释吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool canCross(vector<int>& stones) {
    if(stones[1] != 1) return false;
    int len = stones.size();
    if(len == 2) return true;
    bool dp[len+5][1200]; //在第i个石头并且是跳j步过来的可以不?
    memset(dp,0,sizeof(dp));
    dp[1][1] = true;
    for(int i = 2;i < len;i++){
        for(int j = 1;j < i;j++){   //遍历前面的所有石头
            int dist = stones[i] - stones[j];  //前面的石头一定是跳dist步过来的
            if(dist > 1100) continue;
            dp[i][dist] |= dp[j][dist-1]|dp[j][dist]|dp[j][dist+1];
            if(i == len-1 && dp[i][dist])
            {
                return true;
            }
        }
    }
    return false;
}

硬核的东西来辽~ 各种背包问题！！

一. 01背包

【题目描述】：

一个旅行者有一个最多能装M公斤的背包，现在有n件物品，他们的重量分别是W1，W2…Wn，它们的价值分别是C1，C2……Cn，求旅行者能够获得的最大总价值。

【输入格式】：

第一行：两个整数，M，（背包容量，M<=200）和N（物品数量N<=30）

第2至N+1行，每行两个整数，Wi,Ci,表示每个物品的重量和价值。

【输出格式】：

仅一行，一个数，表示最大总价值。

【输入样例】：
1
2
3
4
5
10 4
2 1
3 3
4 5
7 9

【输出样例】：12

思路：

01背包问题可以说是最简单的背包问题，简单之处在于：它的每个物品只有一个。

首先定义一个f[MAXN][MAXN]数组，用来记录最大值，即f[i][v]表示的是当前i件物品放入一个容量为v的背包的时候可以获得的最大值。

01背包的状态转移方程为: f[i][v] = max(f[i - 1][v], f[i - 1][v - w[i]] + c[i])

解释：如果只考虑第i件物品的方式策略，那么就只和第i - 1件物品有关了，如果是放第i间物品，那么问题就转换为：“前i - 1件物品放入容量为v的背包中”，此时能够获得的最大价值就是f[i - 1][v - w[i]]，也就是第i - 1件物品放入容量为v(原来的总容量)减去w[i](第i间物品的占容产生的价值)，再加上放通过第i件物品增加的价值c[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int bag01() {
    // m表示背包总容量，n表示有n件物品
    int m, n;
    cin >> m >> n;
    int w[n + 1] = {0}, c[n + 1] = {0};
    vector<vector<int>>dp(n + 1, vector<int> (m + 1, 0));
    for(int i = 1;i <= n;i++) {
        cin >> w[i] >> c[i];
    }
    for(int i = 1;i <= n;i++) {
        // 这里需要注意是逆序的，因为保证第i次循环dp[i][j]的状态是从dp[i][j - w[i]]递推而来的，也就是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的绝不可能选入第i件物品的子结果f[i][v - w[i]]
        for(int j = m;j > 0;j--) {
            if(w[i] <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        } 
    }
    return dp[n][m];
}

二. 完全背包问题

【题目描述】

设有n种物品，每种物品有一个价值，但每种物品的数量是无限的，同时有一个背包，最大承载量为m，今从n种物品中选取若干件，（同一种物品可以多次选举）使其重量的和小于等于m，而且价值的和最大。

【输入】

共N+1行

第一行：两个整数：M（背包容量M<=200）和N（物品数量，N<=30）；

第二行至第N+1行，每行两个整数，Wi，Ci，表示每个物品的重量和价值。

【输出】

近一行：一个数，表示最大的价值；

【输入样例】

10 4

2 1

3 3

4 5

7 9

【输出样例】

12

思路：

这一个问题与01背包唯一不同的地方，就是每种物品的数量是无限多的。

既然每种物品可以取很多次，那么，与它相关的策略就不是取或者不取的问题了，而是不取和取多少的问题了。

这个时候，其实我们只需要多一层关于每种物品选多少次的循环就可以了。相对的，状态转移方程也会有相应的改动。

f[i][v] = max(f[i - 1][v], f[i - 1][v - k * w[i]] + k * c[i])