力扣 hot100 -- 动态规划(下)

发布于:2024-07-11 ⋅ 阅读:(25) ⋅ 点赞:(0)

目录

💻最长递增子序列

AC  动态规划

AC  动态规划(贪心) + 二分

🏠乘积最大子数组

AC  动规

AC  用 0 分割

🐬分割等和子集

AC  二维DP

AC  一维DP

⚾最长有效括号

AC  栈 + 哨兵


💻最长递增子序列

300. 最长递增子序列 - 力扣(LeetCode)

子序列:不用连续

子串:要求连续

AC  动态规划

时间 O(n^2)

/*
dp[i] : 第 i 个元素结尾的最长子序列长度(下标0开始)
dp[i] = max(dp[i], dp[j] + 1)
初始化 : dp[i] = 1
*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1, 1);
        for (int i = 1; i < n; ++i)
            for (int j = 0; j < i; ++j) 
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
        int ans = 1;
        for (auto x : dp)
            ans = max(ans, x);
        return ans;
    }
};

AC  动态规划(贪心) + 二分

二分实现 O(logn) 查找,为了使用二分,我们需要让 dp[] 数组有序,所以需要改变 dp[] 数组的含义(状态)

贪心策略:tails 中存储的元素越小,上升的子序列越长 

举例解释

nums[] = {7, 8, 9, 1, 2, 3, 4, 5};

遍历完 7 8 9 后 tails[] = {7, 8, 9};

接着遍历到 1,那么二分查找 tails[],找到第一个比 tails 大的位置,即 7,替换后变成

tails[] = {1, 8, 9};

如果没有比当前 nums[] 值大的元素,直接加到后面

最后输出 tails[] 长度,就是最长上升子序列长度

时间 O(nlogn)

/*
tails[i] : 长度 i+1 子序列的尾部元素
1)nums[] 中当前元素 x > tails.back(), x 插入 tails 最后
2)否则, 二分查找 tails[] 中第一个 > x 的元素, 替换成 x
最后返回 tails[] 大小
*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        tails.push_back(nums[0]);

        for (auto x : nums) {
            if (x > tails.back()) {
                tails.push_back(x);
                continue;
            }
            int l = 0, r = tails.size() - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (tails[mid] < x)
                    l = mid + 1;
                else
                    r = mid;
            }
            tails[l] = x;
        }
        return tails.size();
    }
};
// 检验二分边界
// tails[]: 1 3 5 -- x: 3/4
// tails[]: 1 3 5 7 -- x: 3/4/5

🏠乘积最大子数组

152. 乘积最大子数组 - 力扣(LeetCode)

注意是“连续子数组” 

AC  动规

1)滚动

本题,dp[i] 都是基于 dp[i -1] 得到的,所以可以将一维数组变成一个变量,即 “滚动数组” 

2)坑

遍历数组,更新 3 个 dp 变量时,maxDp 基于上一个 maxDp 没问题

但是 maxDp 更新后,minDp 还是基于上一个 maxDp

所以需要一个临时变量保存上一个 maxDp

然后 dp 可以直接基于新的 maxDp

3)坑2

题目保证 32 位,也就是 10^9,但是,样例里有一组 10^19 次方的....

所以,有 4 个地方要加 double,防止类型不匹配 或 heap flow(堆溢出)

时间 O(n)

/*
滚动数组,一维数组变变量
maxDp[i] : 第 i 个元素结尾的最大值
minDp[i] : 第 i 个元素结尾的最小值
dp[i] : 只选前 i 的元素的最大值
*/
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n == 1)
            return nums[0];
        double maxDp = nums[0], minDp = nums[0], dp = nums[0];
        for (int i = 1; i < n; ++i) {
            double t = maxDp; // 临时变量
            maxDp = max(max((double)nums[i], maxDp*nums[i]), minDp*nums[i]);
            minDp = min(min((double)nums[i], t*nums[i]), minDp*nums[i]);
            dp = max(dp, maxDp); // 上一个 dp 和 新的 maxDp 取较大值
        }
        return (double)dp;
    }
};

AC  用 0 分割

用 0 分割成多个连续的子数组,对每个子数组:

1)偶数个负数,直接相乘(负数数量 0, 2, 4, 6...)

2)奇数个负数:

        a. 左到右相乘,直到最后一个负数之前

        b. 右到左,直到最后一个负数之前

取 a. b. 的 max()

3)实际遍历中,先左到右遍历,后右到左遍历,单次遍历中,只需要动态更新最大值(包含了偶数,奇数个负数的两种情况)

时间 O(n)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        double ans = nums[0];
        double t = 1; // 临时变量保存乘积
        
        // 左到右
        for (int i = 0; i < nums.size(); ++i) {
            t *= nums[i];
            ans = max(ans, t);
            if (t == 0)
                t = 1; // 用 0 分割子数组
        }
        // 右到左
        t = 1;
        for (int i = nums.size() - 1; i >= 0; --i) {
            t *= nums[i];
            ans = max(ans, t);
            if (t == 0)
                t = 1;
        }
        return (int)ans;
    }
};

🐬分割等和子集

416. 分割等和子集 - 力扣(LeetCode)

AC  二维DP

01背包画表格类似这样

和为奇数,直接返回 false,否则打表会发现,出现了一些奇怪的错误

含义

dp[i][j] : 只从 [0, i] 区间里选,每个数最多选 1 次,和为 j

递推式

选第 i 个:dp[i - 1][j - nums[i]]

不选第 i 个:dp[i - 1][j]

第 i 个数 == 总和的一半

dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j] || (nums[i] == sum/2)

初始化

根据递推式,只需初始化第 0 行,即只从 [0, 0] 区间选,和为 nums[0] 的 == 1,其他为 0

输出

dp[n - 1][sum / 2]:表示从 [0, n - 1] 选, 和为总和一半, 即等和子集

O(n * sum/2)

// dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j] || (nums[i] == sum/2)
// 输出 dp[n - 1][sum / 2]
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for (auto x : nums)
            sum += x;
        if (sum % 2 == 1)
            return false; // 和为奇数

        // n 行, 每一行就是 vector<int>(), 这一行表示总和 0 ~ sum/2, 初始化为 0
        vector<vector<int>> dp(n, vector<int>(sum / 2 + 1, 0));

        if (nums[0] <= sum/2)
            dp[0][nums[0]] = 1; // 从 [0, 0] 选, 和为nums[0]

        for (int i = 1; i < n; ++i)
            for (int j = 0; j <= sum/2; ++j) {
                dp[i][j] = dp[i - 1][j] || (nums[i] == sum/2);
                if (j >= nums[i]) // 防止越界
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]];
            }

        return dp[n - 1][sum / 2];
    }
};

AC  一维DP

考虑到递推式 dp[i][j] 都是来源于 dp[i - 1][...],可以将二维变成一维,优化空间👇

那么为什么要逆序遍历子集的和 j 呢,因为,dp[j] 都是基于上一行的,旧的(未被修改的) dp[j] 和 dp[j - nums[i]]

如果顺序遍历,dp[j - nums[i]] 会被多次修改,也就是取了多个元素,而题目规定只能取一个

顺序遍历适合完全背包,而不是 01 背包

 

// dp[j] :和为 j
// dp[j] = dp[j - nums[i]] || dp[j] || (nums[i] == sum/2)
// 输出 dp[sum / 2]
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for (auto x : nums)
            sum += x;
        if (sum % 2 == 1)
            return false; // 和为奇数

        // 和的一半 +1 个元素
        vector<int> dp(sum / 2 + 1, 0);

        if (nums[0] <= sum/2)
            dp[nums[0]] = 1; // 从 [0, 0] 选, 和为nums[0]

        for (int i = 1; i < n; ++i)
            for (int j = sum/2; j >= 0; --j) {
                dp[j] = dp[j] || (nums[i] == sum/2);
                if (j >= nums[i]) // 防止越界
                    dp[j] = dp[j] || dp[j - nums[i]];
            }
        return dp[sum / 2];
    }
};

⚾最长有效括号

32. 最长有效括号 - 力扣(LeetCode)

AC  栈 + 哨兵

求连续的最长有效括号

如果不连续,栈就会被清空最后一个元素,再插入新的下标,即更新了栈顶的元素

初始插入 -1(哨兵),防止先遇到右括号,栈为空就 pop 导致的栈溢出

时间 O(n)

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        if (s.size() == 0) return 0;

        stack<int> st;
        st.push(-1); // 防止溢出, 为后面的连续准备

        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') // 左括号
                st.push(i); 
            else { // 右括号
                st.pop();
                if (st.empty())
                    st.push(i);
                else 
                    ans = max(ans, i - st.top()); // 连续的长度
            }
        }
        return ans;
    }
};