1. Toy模板网首页
  2. > Toy博客

15.动态规划：数据结构优化DP

8月前 作者：Miraclo_acc 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了15.动态规划：数据结构优化DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构优化DP有前缀和、滑动窗口、树状数组、线段树、单调栈、单调队列

树状数组优化DP

300. 最长递增子序列【值域树状数组】

中等

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

朴素解法

方法一：枚举选哪个 O(n^2)

方法二：贪心+二分查找 O(nlogn)。交换状态和状态值 dp[i] 表示末尾元素为 nums[i] 的LIS长度 == > g[i] 表示长度为 i+1 的LIS 的末尾元素的最小值

一个新员工一个老员工价值相当，老员工就可以走了，因为新员工被榨取的剩余空间更多。

class Solution {
    /**
    方法一：O(n^2)
    定义 f[i]表示以i结尾的递增子序列的长度
    转移 f[i] = f[j] + 1 , 其中j满足0<j<i && nums[j] < nums[i]
     */
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int ans = 0;
        Arrays.fill(f, 1);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    f[i] = Math.max(f[i], f[j]+1);
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

class Solution {
    /**
    方法二：O(nlogn)
    定义 f[i] 表示长度为i的子序列末尾元素为f[i]
     */
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int len = 0;
        int[] f = new int[n];
        for(int x : nums){
            // 二分找到 >= x 的第一个下标
            int left = 0, right = len;
            while(left < right){
                int mid = (left + right) >> 1;
                if(f[mid] < x) left = mid + 1;
                else right = mid;
            }
            f[right] = x;
            if(right == len) // 如果更新值=len，则长度+1
                len++;
        }
        return len;
    }
}

树状数组、线段树优化

具体来说，定义 f [ i ] [ j ] f[i][j] f[i][j] 表示 nums \textit{nums} nums 的前 i i i个元素中，以元素 j j j 结尾的满足条件的子序列的最长长度。

  • 当 j ≠ nums [ i ] j\ne\textit{nums}[i] j=nums[i] 时， f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] = f[i-1][j] f[i][j]=f[i−1][j]。
  • 当 j = nums [ i ] j=\textit{nums}[i] j=nums[i] 时，我们可以从 f [ i − 1 ] [ j ′ ] f[i-1][j'] f[i−1][j′] 转移过来，这里 j ′ < j j'<j j′<j，取最大值，得 f [ i ] [ j ] = 1 + max ⁡ j ′ = 0 j − 1 f [ i − 1 ] [ j ′ ] f[i][j] = 1 + \max_{j'=0}^{j-1} f[i-1][j'] f[i][j]=1+maxj′=0j−1​f[i−1][j′]

上式有一个「区间求最大值」的过程，这非常适合用线段树计算，且由于 f [ i ] f[i] f[i] 只会从 f [ i − 1 ] f[i-1] f[i−1] 转移过来，我们可以把 f f f 的第一个维度优化掉。这样我们可以用线段树表示整个 j j j 数组，在上面查询和更新。

最后答案为 max ⁡ ( f [ n − 1 ] ) \max(f[n-1]) max(f[n−1])，对应到线段树上就是根节点的值。

使用滚动数组优化，可以去掉第一个条件，等价于单点修改，区间查询的问题

f[i] = f[j] + 1

  • 等号左侧：单点修改
  • 等号右侧：区间求max

===>树状数组、线段树维护「区间最大值」

class Solution {
    /**
    1. 先对nums节点离散化
    2. 每次都找比当前数小的最长递增序列，不断更新结果
     */
    public int lengthOfLIS(int[] nums) {
        // 离散化
        Set<Integer> set = new HashSet<>(); // 防止重复
        for(int x : nums) set.add(x);
        List<Integer> copy = new ArrayList<>(set);
        Collections.sort(copy);

        int res = 0;
        // 值域树状数组，用树状数组维护以元素值j结尾的最长子序列长度
        BIT tree = new BIT(copy.size()+1);
    for(int num : nums){
        // 二分找到 >= nums 的第一个下标, 查找的元素一定存在
        int left = 0, right = copy.size();
        while(left < right){
            int mid = (left + right) >> 1;
            if(copy.get(mid) < num) left = mid + 1;
            else right = mid;
        }
        int k = right+1; // right即查找的元素，这里+1是因为树状数组下标从1开始

        // 更新答案，查找以元素值(1,num-1)结尾的LIS的最大值
        res = Math.max(res, (int)tree.preMax(k) + 1);
        // 维护树状数组，更新以元素值(1,num)结尾的LIS的最大值
        tree.update(k+1, (int)tree.preMax(k) + 1);
    }
    return res;
}
}

// 树状数组模板（维护前缀最大值）
class BIT {
    private long[] tree;

    public BIT(int n) {
        tree = new long[n];
        Arrays.fill(tree, Long.MIN_VALUE);
    }

    public void update(int i, long val) {
        while (i < tree.length) {
            tree[i] = Math.max(tree[i], val);
            i += i & -i;
        }
    }

    public long preMax(int i) {
        long res = Long.MIN_VALUE;
        while (i > 0) {
            res = Math.max(res, tree[i]);
            i &= i - 1;
        }
        return res;
    }
}

2926. 平衡子序列的最大和

困难

给你一个下标从 0 开始的整数数组 nums 。

nums 一个长度为 k 的 子序列 指的是选出 k 个 下标 i0 < i1 < ... < ik-1 ，如果这个子序列满足以下条件，我们说它是 平衡的 ：

  • 对于范围 [1, k - 1] 内的所有 j ，nums[ij] - nums[ij-1] >= ij - ij-1 都成立。

nums 长度为 1 的 子序列 是平衡的。

请你返回一个整数，表示 nums 平衡 子序列里面的 最大元素和 。

一个数组的 子序列 指的是从原数组中删除一些元素（也可能一个元素也不删除）后，剩余元素保持相对顺序得到的 非空 新数组。

示例 1：

输入：nums = [3,3,5,6]
输出：14
解释：这个例子中，选择子序列 [3,5,6] ，下标为 0 ，2 和 3 的元素被选中。
nums[2] - nums[0] >= 2 - 0 。
nums[3] - nums[2] >= 3 - 2 。
所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。
包含下标 1 ，2 和 3 的子序列也是一个平衡的子序列。
最大平衡子序列和为 14 。

示例 2：

输入：nums = [5,-1,-3,8]
输出：13
解释：这个例子中，选择子序列 [5,8] ，下标为 0 和 3 的元素被选中。
nums[3] - nums[0] >= 3 - 0 。
所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。
最大平衡子序列和为 13 。

示例 3：

输入：nums = [-2,-1]
输出：-1
解释：这个例子中，选择子序列 [-1] 。
这是一个平衡子序列，而且它的和是 nums 所有平衡子序列里最大的。

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
class Solution {
    /**
    nums[ij] - nums[ij-1] >= ij - ij-1
    nums[i] - nums[j] >= i - j
    ==> nums[i] - i >= nums[j] - j
    定义 b[i] = nums[i] - i
    b[i] >= b[j]  
    ==> 问题变为从 b 中选一个子序列，满足这个子序列是一个非递减的序列
            求对应的元素和的最大值
    a 3 3 5 6
    b 3 2 4 3

    定义 f[i] = 以下标 i 结尾的子序列，对应的 nums 的元素和的最大值
    转移 f[i] = f[j] + nums[i], 其中 j 满足 (j < i && b[j] <= b[i])
    使用值域树状数组优化，
        等式左边 单点修改
        等式右边 区间查询
    
    BIT用来维护前缀最大值，设下标为x=b[i],维护的值为max(f[x], f[x-1], f[x-2]..)
    实现时，需要先把nums[i] - i离散化
     */
    public long maxBalancedSubsequenceSum(int[] nums) {
        int n = nums.length;
        int[] b = new int[n];
        for(int i = 0; i < n; i++){
            b[i] = nums[i] - i;
        }
        Arrays.sort(b);

        BIT t = new BIT(b.length+1);
        for(int i = 0; i < n; i++){
            // j 为 nums[i]-i 离散化后的值（从 1 开始）
            int j = Arrays.binarySearch(b, nums[i] - i) + 1;
            long f = Math.max(t.preMax(j), 0) + nums[i];
            t.update(j, f);
        }
        return t.preMax(b.length);
    }
}

// 树状数组模板（维护前缀最大值）
class BIT {
    private long[] tree;

    public BIT(int n) {
        tree = new long[n];
        Arrays.fill(tree, Long.MIN_VALUE);
    }

    public void update(int i, long val) {
        while (i < tree.length) {
            tree[i] = Math.max(tree[i], val);
            i += i & -i;
        }
    }

    public long preMax(int i) {
        long res = Long.MIN_VALUE;
        while (i > 0) {
            res = Math.max(res, tree[i]);
            i &= i - 1;
        }
        return res;
    }
}

线段树优化DP

300. 最长递增子序列【值域线段树】

中等

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

树状数组、线段树优化

具体来说，定义 f [ i ] [ j ] f[i][j] f[i][j] 表示 nums \textit{nums} nums 的前 i i i个元素中，以元素 j j j 结尾的满足条件的子序列的最长长度。

  • 当 j ≠ nums [ i ] j\ne\textit{nums}[i] j=nums[i] 时， f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] = f[i-1][j] f[i][j]=f[i−1][j]。
  • 当 j = nums [ i ] j=\textit{nums}[i] j=nums[i] 时，我们可以从 f [ i − 1 ] [ j ′ ] f[i-1][j'] f[i−1][j′] 转移过来，这里 j ′ < j j'<j j′<j，取最大值，得 f [ i ] [ j ] = 1 + max ⁡ j ′ = 0 j − 1 f [ i − 1 ] [ j ′ ] f[i][j] = 1 + \max_{j'=0}^{j-1} f[i-1][j'] f[i][j]=1+maxj′=0j−1​f[i−1][j′]

上式有一个「区间求最大值」的过程，这非常适合用线段树计算，且由于 f [ i ] f[i] f[i] 只会从 f [ i − 1 ] f[i-1] f[i−1] 转移过来，我们可以把 f f f 的第一个维度优化掉。这样我们可以用线段树表示整个 j j j 数组，在上面查询和更新。

最后答案为 max ⁡ ( f [ n − 1 ] ) \max(f[n-1]) max(f[n−1])，对应到线段树上就是根节点的值。

使用滚动数组优化，可以去掉第一个条件，等价于单点修改，区间查询的问题

f[i] = f[j] + 1

  • 等号左侧：单点修改
  • 等号右侧：区间求max

===>树状数组、线段树维护「区间最大值」

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 离散化
        Set<Integer> set = new HashSet<>(); // 防止重复
        for(int x : nums) set.add(x);
        List<Integer> copy = new ArrayList<>(set);
        Collections.sort(copy);

        N = copy.size();
        int ans = 0;
        for(int num : nums){
            // 二分找到 >= nums 的第一个下标, 查找的元素一定存在
            int left = 0, right = copy.size();
            while(left < right){
                int mid = (left + right) >> 1;
                if(copy.get(mid) < num) left = mid + 1;
                else right = mid;
            }
            int k = right; // num 对应的下标 k
            // 查找以元素值(1,num-1)结尾的LIS的最大值
            int cnt = 1 + query(root,0,N,0,k-1);
            // 更新 值[k]的最大值
            // 注意这里是覆盖更新，对应的模版中覆盖更新不需要累加
            update(root,0,N,k,k,cnt);
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
    
    class Node {
        // 左右孩子节点
        Node left, right;
        // 当前节点值，以及懒惰标记的值
        int val, add;
    }
    private int N = (int) 1e9;
    private Node root = new Node();
    public void update(Node node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            node.val = val;
            node.add = val;
            return;
        }
        pushDown(node);
        int mid = (start + end) >> 1;
        if (l <= mid) update(node.left, start, mid, l, r, val);
        if (r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }
    public int query(Node node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return node.val;
        pushDown(node);
        int mid = (start + end) >> 1, ans = 0;
        if (l <= mid) ans = query(node.left, start, mid, l, r);
        if (r > mid) ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
        return ans;
    }
    private void pushUp(Node node) {
        // 每个节点存的是当前区间的最大值
        node.val = Math.max(node.left.val, node.right.val);
    }
    private void pushDown(Node node) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return;
        node.left.val = node.add;
        node.right.val = node.add;
        node.left.add = node.add;
        node.right.add = node.add;
        node.add = 0;
    }
}

单调队列优化DP

单调队列就是一种队列内的元素有单调性（单调递增或者单调递减）的队列，最优解存在队首，而队尾则是最后进队的元素。

单调队列用来维护区间最值或者降低DP的维数来减少空间及时间

利用单调队列对dp方程进行优化，可将O(n)复杂度降至O(1)

  • N 维的DP，可以优化为 N-1 维 !!!

单调队列适合优化决策取值范围的上、下界均单调变化的问题。

并不是所有DP都可以由单调队列优化，像最大化、最小化决策的结果，即决策具有单调性的题目可以优化。

🚀1425. 带限制的子序列和

困难

给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。

示例 1：

输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。

示例 2：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。

示例 3：

输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。

提示：

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

https://leetcode.cn/problems/constrained-subsequence-sum/solutions/220273/dpdan-diao-zhan-you-hua-xiang-jie-by-wangdh15/

class Solution {
    /**
    定义f[i]表示以i结尾的最大子序列和，考虑第 i 个元素选还是不选
        接在后面 f[i] = max(dp[i-j] + nums[i]) , 其中 j < i 且 i-j<=k
        不接，重新做起点 f[i] = nums[i]
        取最大值
    如果枚举所有元素作为结尾的话，时间复杂度O(nk)，会超时，如何优化？
    
    由于当前时刻只依赖于前k个时刻的状态，所以只要快速找到前k个状态中的最大子序列和即可
        ==> 滑动窗口求最大值
     */
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] f = new int[n]; // 定义f[i]表示以i结尾的最大子序列和
        // 维护单增队列，队首为最大值，保存 (以下标为结尾的子序列和，下标)
        Deque<int[]> dq = new ArrayDeque<>();
        int res = nums[0];
        for(int i = 0; i < n; i++){
            f[i] = nums[i]; // 不接
            if(!dq.isEmpty()){ // 接
                f[i] = Math.max(f[i], dq.peekFirst()[0] + nums[i]);
            }
            res = Math.max(res, f[i]);
            // 清除队列中无用的元素
            while(!dq.isEmpty() && dq.peekLast()[0] <= f[i]){
                dq.pollLast();
            }
            dq.addLast(new int[]{f[i], i});
            if(!dq.isEmpty() && dq.peekFirst()[1] == i - k)
                dq.pollFirst();
        }
        return res;
    }
}

1687. 从仓库到码头运输箱子

困难

你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。

给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，其中 boxes[i] = [portsi, weighti] 。

  • portsi 表示第 i 个箱子需要送达的码头， weightsi 是第 i 个箱子的重量。
  • portsCount 是码头的数目。
  • maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重量的限制。

箱子需要按照 数组顺序 运输，同时每次运输需要遵循以下步骤：

  • 卡车从 boxes 队列中按顺序取出若干个箱子，但不能违反 maxBoxes 和 maxWeight 限制。
  • 对于在卡车上的箱子，我们需要 按顺序 处理它们，卡车会通过 一趟行程 将最前面的箱子送到目的地码头并卸货。如果卡车已经在对应的码头，那么不需要 额外行程 ，箱子也会立马被卸货。
  • 卡车上所有箱子都被卸货后，卡车需要 一趟行程 回到仓库，从箱子队列里再取出一些箱子。

卡车在将所有箱子运输并卸货后，最后必须回到仓库。

请你返回将所有箱子送到相应码头的 最少行程 次数。

示例 1：

输入：boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3
输出：4
解释：最优策略如下：
- 卡车将所有箱子装上车，到达码头 1 ，然后去码头 2 ，然后再回到码头 1 ，最后回到仓库，总共需要 4 趟行程。
所以总行程数为 4 。
注意到第一个和第三个箱子不能同时被卸货，因为箱子需要按顺序处理（也就是第二个箱子需要先被送到码头 2 ，然后才能处理第三个箱子）。

示例 2：

输入：boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6
输出：6
解释：最优策略如下：
- 卡车首先运输第一个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第二、第三、第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第五个箱子，到达码头 2 ，回到仓库，总共 2 趟行程。
总行程数为 2 + 2 + 2 = 6 。

示例 3：

输入：boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7
输出：6
解释：最优策略如下：
- 卡车运输第一和第二个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第三和第四个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第五和第六个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
总行程数为 2 + 2 + 2 = 6 。

示例 4：

输入：boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount = 5, maxBoxes = 5, maxWeight = 7
输出：14
解释：最优策略如下：
- 卡车运输第一个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第二个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第三和第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第五个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第六和第七个箱子，到达码头 3 ，然后去码头 4 ，然后回到仓库，总共 3 趟行程。
- 卡车运输第八和第九个箱子，到达码头 1 ，然后去码头 5 ，然后回到仓库，总共 3 趟行程。
总行程数为 2 + 2 + 2 + 2 + 3 + 3 = 14 。

提示：

  • 1 <= boxes.length <= 105
  • 1 <= portsCount, maxBoxes, maxWeight <= 105
  • 1 <= portsi <= portsCount
  • 1 <= weightsi <= maxWeight

https://leetcode.cn/problems/delivering-boxes-from-storage-to-ports/solutions/2006470/by-lcbin-xwzl/文章来源地址https://www.toymoban.com/news/detail-773256.html

class Solution {
    /**
    定义f[i]表示运送前i个箱子需要的最小行程次数
    转移,枚举上一次运送的状态，包括[1,2,3...maxBoxeds]个箱子,i可以从j转移过来
    f[i] = f[j-1] + cost[j, i] (i - maxB+1 <= j <= i)
            cost[j, i] 表示第k~第i个箱子的行程次数
    枚举所有以i结尾的行程会超时 O(n^2)，如何优化？

    实际上我们是要在[i-maxBoxeds,..i-1]这个窗口内找到一个j，
                                使得f[j] - cost[j]的值最小，
    问题变为求滑动窗口的最小值
    
    如何优化码头i到j的行程数？取决于相邻两个码头是否相等
    我们可以通过前缀和，计算出码头之间的行程数，再加上首尾两趟行程，就能O(1)计算
    重量同理
     */
    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
        int n = boxes.length;
        long[] ws = new long[n+1];
        int[] cs = new int[n];
        for(int i = 0; i < n; i++){
            int p = boxes[i][0], w = boxes[i][1];
            ws[i+1] = ws[i] + w;
            if(i < n-1){
                cs[i+1] = cs[i] + (p != boxes[i+1][0] ? 1 : 0);
            }
        }
        int[] f = new int[n+5];
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(0);
        for(int i = 1; i <= n; i++){
            while(!dq.isEmpty() && (i - dq.peekFirst() > maxBoxes || 
                                    ws[i] - ws[dq.peekFirst()] > maxWeight)){
                dq.pollFirst();                        
            }
            if(!dq.isEmpty()){
                f[i] = cs[i-1] + f[dq.peekFirst()] - cs[dq.peekFirst()] + 2;
            }
            if(i < n){
                while(!dq.isEmpty() && f[dq.peekLast()] - cs[dq.peekLast()] >= f[i] - cs[i]){
                    dq.pollLast();
                }
                dq.addLast(i);
            }
        }
        return f[n];
    }
}

到了这里，关于15.动态规划：数据结构优化DP的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 动态规划——斜率优化DP 学习笔记

    动态规划——斜率优化DP 学习笔记

    适用于求解最优解（最大、最小）问题。 可以将转移方程可以化为 (left[begin{array}{rl} 仅与 space i space 有关 是我们想要最大/最小化的 \\\\ 仅与 space j space 有关 是已知的 \\\\ 与 space i space 和 space j space 都有关 是两项相乘 end{array}right]) 三部分的， 都可以考虑用斜率优化

    2024年02月08日
    浏览(42)

  • 动态规划——矩阵优化DP 学习笔记

    前置知识：矩阵、矩阵乘法。 斐波那契数列 在斐波那契数列当中， (f_1 = f_2 = 1) ， (f_i = f_{i - 1} + f_{i - 2}) ，求 (f_n) 。 而分析式子可以知道，求 (f_k) 仅与 (f_{k - 1}) 和 (f_{k - 2}) 有关； 所以我们设矩阵 (F_i = begin{bmatrix} f_{i - 1} f_{i - 2} end{bmatrix}) 。 设矩阵 (text{Ba

    2024年02月08日
    浏览(48)
  • 数据结构与算法-动态规划

    数据结构与算法-动态规划

    （我猜是做的多了背的题多了就自然懂了） 迭代法一般没有通用去重方式,因为已经相当于递归去重后了 这两个问题其实是一个问题,一般直接写出的没有去重的递归法,复杂度很高,此时需要使用备忘录去重,而备忘录去重时间复杂度和使用dp数组进行迭代求解时间复杂度相同

    2024年02月04日
    浏览(36)
  • python算法与数据结构---动态规划

    python算法与数据结构---动态规划

    记不住过去的人，注定要重蹈覆辙。 对于一个模型为n的问题，将其分解为k个规模较小的子问题（阶段），按顺序求解子问题，前一子问题的解，为后一子问题提供有用的信息。在求解任一子问题时，通过决策求得局部最优解，依次解决各子问题。最后通过简单的判断，得到

    2024年02月20日
    浏览(40)
  • 数据结构与算法之贪心&动态规划

    数据结构与算法之贪心&动态规划

            一：思考         1.某天早上公司领导找你解决一个问题，明天公司有N个同等级的会议需要使用同一个会议室，现在给你这个N个会议的开始和结束 时间，你怎么样安排才能使会议室最大利用？即安排最多场次的会议？电影的话 那肯定是最多加票价最高的，入场

    2024年02月09日
    浏览(38)
  • 【数据结构】动态规划（Dynamic Programming）

    【数据结构】动态规划（Dynamic Programming）

    求解决策过程（decision process）最优化的数学方法。 将多阶段决策过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。 与分治法类似，将待求解问题 分解成若干个子问题 。 但是经分解得到的子问题往往 不是相互独立 的。 如果使用分治法求解问题，有些子问

    2024年02月03日
    浏览(35)
  • 动态规划——带权二分优化DP 学习笔记

    动态规划——带权二分优化DP 学习笔记

    带权二分其实并不一定用于优化 DP，也可能用于优化贪心等最优化的算法。 带权二分也叫 WQS 二分，最初由王钦石在他的 2012 年国家集训队论文中提出。 使用情况 要解决一个最优化问题（求最大 / 最小值） 有一个限制，一般是某个参数要求一定恰好为 (k) 而带权二分就可以

    2024年02月08日
    浏览(30)
  • 动态规划——决策单调性优化DP 学习笔记

    动态规划——决策单调性优化DP 学习笔记

    对于最优性问题，常有状态转移方程： (f_i = min/max{f_jdots}) ， 形象的：如果 (i) 的最优转移点是 (j) ， (i\\\') 的最优转移点是 (j\\\') ，当 (ii\\\') 时，有 (jle j\\\') ，则称该 DP 问题具有决策单调性。 即： (i) 单增，其最优转移点单调不减。 如何发现一个转移方程具有决策

    2024年02月08日
    浏览(41)
  • 从01背包开始动态规划：暴力解法 + dp + 滚动数组 + dp优化

    从01背包开始动态规划：暴力解法 + dp + 滚动数组 + dp优化

        01背包问题是动态规划中最经典的问题之一，本篇将通过给出其四种解法，使读者更深刻理解动态规划。   有N件物品和一个容量是 V 的背包，每个物品有各自的体积和价值，且每个物品只能放一次（这也是01背包名字的由来），如何让背包里装入的物品具有最大的价值总

    2024年04月17日
    浏览(41)
  • Java数据结构与算法----动态规划（背包篇）

    Java数据结构与算法----动态规划（背包篇）

    1.1.算法思路 0/1背包是动态规划、背包问题中最经典的问题啦！它主要的问题是： 给定n种物品、这n种物品的重量分别是，价值分别是 ，而你有一个容量为C的背包，请问如何求出所能拿的最大价值呢？ 对于动态规划，我们先需要找到一条推导公式，然后确定边界： 我们设

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包