标签: dynamic-programming

我正在尝试解决这个练习：我们有 n 个物品，其中每个物品都有一个给定的非负重量 w1,w2,...,wn 和值 v1,v2,...,vn，以及一个具有最大重量容量的背包W. 我必须找到最大值的子集 S，受两个限制：1）集合的总权重不应超过 W；2）我不能接受具有连续索引的对象。

例如，当 n = 10 时，可能的解为 {1, 4, 6, 9}, {2, 4, 10} o {1, 10}。

我怎样才能建立一个正确的重复？

我正在使用动态编程使用 Levenshtein（编辑）距离做一些工作。我想我理解 Wagner-Fischer 算法可以有效地做到这一点。但是，该算法看起来并不具有建设性。如果我计算出两个字符串之间的编辑距离是，例如，10，那么我还想确定一个特定的 10 个编辑序列，将一个转换为另一个。这也可以有效地完成吗？如果是这样，如何？

我正在尝试解决我之前问过的一个问题的变体：

给定一串括号（长度 <= 1,000,000）和范围查询列表，为 <= 100,000 查询中的每一个查询在每个范围内找到平衡括号的最长子序列

我发现了另一个类似的问题，但只有一个 O(N^3) 算法。

我相信这种形式的 DP 解决方案dp[i, j] = longest balanced subsequence in [i .. j]应该可以工作，因为一旦计算，这将能够仅通过查询 DP 表来回答所有范围查询。然而，由于可能的输入字符串长度很大，即使是这个问题的 O(N^2) 解决方案也会超过时间限制。

此外，使用堆栈跟踪匹配括号的技巧不再直接有效，因为您正在寻找子序列，而不是子字符串。

我有一种我认为可能有效但不确定的方法：

一个区间内平衡括号的最长子序列的长度是该区间内平衡括号的最长非重叠子串的长度之和。

例如，如果您有字符串

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

) ) ( ( ) ( ( ) ) ) ) ( ( ) )

区间[0, 8]（含）内平衡括号的最长子序列长度为5，该长度等于区间内最长非重叠子串的长度之和：“( )” + "( ( ) )"。

这种方法会一直有效，还是有更好的方法？

谁能提供两个字符串之间最长公共子串的记忆方法。我知道最底层的解决方案，但我无法以自上而下的方式思考。预期时间复杂度-O(n^2)

我正在阅读关于 cormen 的动态编程。

相关背景可以在以下链接中找到

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap16.htm

通常，子问题图提供了一种替代方法来执行动态编程的运行时分析。每个顶点对应一个子问题，子问题的选择是从该子问题入射的边。回想一下，在杆切割中，子问题图有 n 个顶点，每个顶点最多有 n 条边，运行时间为 O(n^2)。对于矩阵链乘法，如果我们要绘制子问题图，它将有 O(n^2) 个顶点，每个顶点的度数最多为 n - 1，总共有 O(n^3) 个顶点和边.

我正在寻找简单示例 n = 4 的矩阵链乘法子问题图。

感谢您的时间和帮助

直接来自 CTCI，8.14：给定一个由符号 0（假）、1（真）、&（与）、| 组成的布尔表达式 (OR) 和 ^(XOR) 以及所需的布尔结果值 result 实现一个函数来计算将表达式括起来的方式的数量，以便它评估结果。

我正在尝试一种蛮力方法来计算每个可能的组合，如果匹配所需的结果，则将其添加到数组（组合）并返回该结果长度。它似乎适用于大多数表达式，但不适用于给出的第二个示例。我似乎缺少什么？

function countEval(s, goalBool, combos = []) {
    // on first call make s into array since theyre easier to work with
    if (!(s instanceof Array)) {
        // and turn 1s and 0s into their bool equivalent
        s = s.split('').map((item) => {
            if (item === '1') {
                return true;
            } else if (item === '0'){
                return false;
            } else {
                return item;
            }
        });
    }
    if (s.length === 1 …

I'm struggling a bit with dynamic programming. To be more specific, implementing an algorithm for finding Fibonacci numbers of n.

I have a naive algorithm that works:

int fib(int n) {
    if(n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

But when i try to do it with memoization the function always returns 0:

int fib_mem(int n) {
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}

I've …

解决与背包问题相关的问题的最佳方法是什么？背包问题有 3 个变量，例如：价值、重量和体积？（最大可能的值，最大重量和体积限制）

我曾尝试使用定义的索引，基于其值/（权重*体积），但我相信这不会给我最好的解决方案，所以我进行了搜索，有些人建议使用动态编程，但所有与此相关的主题，只有 2 个变量（值和权重），我不知道超过 2 个变量会如何影响这一点。

解决这个问题的合乎逻辑的方法是什么？我在这里找到了解决方案：代码看起来很简单的解决方案，但我在逻辑上很难理解它。

从同一个博客我无法理解这一行，

所以以1结尾的数等于DP[n-1]。

有没有更简单的方法可以解释这个解决方案？

所以我最近一直在学习动态规划 (DP)，当我遇到以下问题时，我决定使用 DP，但由于我是算法的初学者，我不确定这是否是 DP 的有效示例。

问题：

给定一个数组 nums。我们将数组的运行总和定义为 runningSum[i] = sum(nums[0]…nums[i])。返回 nums 的运行总和。

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

这是我的“DP”解决方案：

class Solution {
    public int[] runningSum(int[] nums) {
        int[] arr = new int[nums.length];
        
        int sum = 0;
        
        for(int i = 0; i < nums.length; i++){
            arr[i] = nums[i] + sum;
            sum += nums[i];
        }
        
        return arr;
    }
}