标签: dynamic-programming

Is it "good practice" to create a class like the one below that can handle the memoization process for you? The benefits of memoization are so great (in some cases, like this one, where it drops from 501003 to 1507 function calls and from 1.409 to 0.006 seconds of CPU time on my computer) that it seems a class like this would be useful.

However, I've read only negative comments on the usage of eval(). Is this usage of …

给定包含符号{true,false,和,或xor}的布尔表达式,计算括号表达式的方式的数量,使其计算结果为true.

例如,只有一种方法可以将'true和false xor true'括起来,使其计算结果为true.

这是我的算法

we can calculate the total number of parenthesization of a string
Definition:  
N - the total number of 
True -  the number of parenthesizations that evaluates to true
False - the number of parenthesizations that evaluates to false
True + False = N 
Left_True - the number of parenthesization in the left part that evaluates to True
same to Left_False, Right_True, Right_False

we iterate the input string from left to right and deal with each …

这是问题描述:

假设我们想知道N层建筑中的哪些故事可以安全地从中掉落鸡蛋,哪些会导致鸡蛋在着陆时破裂.我们做了一些假设:可以再次使用在摔倒后存活的鸡蛋.

• 必须丢弃破蛋.
• 所有鸡蛋的跌倒效果都是一样的.
• 如果鸡蛋在掉落时断裂,那么如果从较高的窗口掉落则会破裂.
• 如果一个鸡蛋在摔倒后存活,那么它会在较短的摔倒后存活.
• 不排除一楼的窗户打破鸡蛋,也不排除N楼的窗户不会导致鸡蛋破裂.

给定一个N层建筑和一个鸡蛋供应,找到最小化(在最坏的情况下)确定断裂所需的实验滴数的策略.

我已经看到并解决了2个鸡蛋的问题,其中答案是14 = N = 100.我尝试使用DP了解wiki的通用解决方案,但无法理解他们想要做什么.请告诉他们他们是如何到达DP以及它是如何工作的？

编辑:

本条中给出的最高流量可用d滴和e蛋测试的复发如下:

f[d,e] = f[d-1,e] + f[d-1,e-1] + 1

复发很好,但我无法理解它是如何衍生出来的？

这个解释对我来说并不清楚....我只是希望有人用更清晰的话语向我解释这种情况.

在n个字符的序列S中; 每个字符可能在序列中出现多次.你想找到S的最长子序列,其中所有出现的相同字符都在一个地方;

对于前者 如果S = aaaccaaaccbccbbbab,那么最长的这样的子序列(答案)是aaaaaaccccbbbb ie = aaa__aaacc_ccbbbb.

换句话说,S中出现的任何字母字符可能只出现在子序列中的一个连续块中.如果可能,给出一个多项式时间算法来确定解.

有谁知道如何将EntityReference转换为实体.

protected override void Execute(CodeActivityContext executionContext)
{
    [Input("Email")]
    [ReferenceTarget("email")]
    public InArgument<Entity> EMail { get; set; }


    Entity MyEmail = EMail.Get<Entity>(executionContext);

这给了我一个错误.无法转换此.

这是"算法导论"第3版的练习15.5-4,这是关于Knuth对最优二叉搜索树的DP方法的改进.

最优二叉搜索树的DP算法是:

OPTIMAL_BST(p, q, n)
let e[1..n+1, 0..n], w[1..n+1, 0..n], and root[1..n, 1..n] be new tables
for i = 1 to n+1
    e[i, i - 1] = q[i - 1];
    w[i, i - 1] = q[i - 1];
for l = 1 to n
    for i = 1 to n - l + 1
        j = i + l - 1
        e[i, j] = INFINITY
        w[i, j] = w[i, j - 1] + p[j] + q[j]
        for r = i …

这是最近在一次采访中向朋友询问的,除了简单的O(n ³)之外,我们不知道任何解决方案.

有更好的算法吗？

问题是在整数数组中找到所有三元组,其总和小于或等于给定的总和S.

注意:我已经在SO上看到了其他类似的问题,性能为O(n ² log n),但是所有这些问题都解决了这个问题的简单版本,比如arr[i] + arr[j] + arr[k] = S他们只在哪里检查是否存在这样的三元组.

我的问题是找出所有i,j,k在arr[]这样arr[i] + arr[j] + arr[k] <= S

有一个A包含(正和负)整数的数组.找到一个(连续的)子数组,其元素的绝对和是最小的,例如:

A = [2, -4, 6, -3, 9]
|(?4) + 6 + (?3)| = 1 <- minimal absolute sum

我已经通过实施蛮力算法,这是开始O(N^2)还是O(N^3),虽然它产生正确的结果.但任务规定:

complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)

经过一番搜索,我认为也许可以修改Kadane的算法以适应这个问题,但我没有做到.

我的问题是 - 卡丹的算法是正确的方法吗？如果没有,你能指出我正确的方向(或命名一个可以帮助我的算法)？我不想要现成的代码,我只需要帮助找到合适的算法.

我们有这种算法在O(n)时间内找到给定序列中的最大正子序列.任何人都可以提出类似的算法来找到最小的正连续子序列.

例如,如果给定的序列是1,2,3,4,5,答案应该是1. [5,-4,3,5,4] - > 1是元素[5,-4]的最小正和.

考虑以下输入的典型背包问题.

V = [10,8,12]
W = [2,3,7]
i =  1,2,3
C = 10

我尝试使用memoization进行递归来解决此示例但发现没有重叠的子问题.

递归程序的签名:

knapsack(int c, int i) 

最初称为 knapsack(10,1)

解决方案的方法类似于https://www.youtube.com/watch?v=6h6Fi6AQiRM和https://www.youtube.com/watch?v=ocZMDMZwhCY中所述.

动态编程如何帮助减少这些Knapsack样本的时间复杂度？如果它没有帮助改善这种情况的时间复杂度,那么DP解决方案的最坏情况复杂性也与基于后向跟踪搜索相同,即2到功率n [ 忽略修剪,就像修剪应用那样复杂性将降低两者解决方案再次DP将不会比非memoized递归解决方案更好 ]

**在上面的示例中是否真的缺少子问题,或者我遗漏了什么？**