我最近发现了一个竞赛问题,要求您计算字符串中必须插入的最小字符数(任何地方)以将其转换为回文结构.

例如,给定字符串:"abcbd"我们可以通过插入两个字符将其转换为回文:一个在"a"之后,另一个在"d"之后:"a d bcbd a ".

这似乎是一个类似问题的概括,要求同样的事情,除了字符只能在最后添加 - 这在使用哈希表的O(N)中有一个非常简单的解决方案.

我一直试图修改Levenshtein距离算法来解决这个问题,但还没有成功.任何有关如何解决这个问题的帮助(它不一定非常有效,我只对任何DP解决方案感兴趣)将不胜感激.

给出N个硬币的列表,它们的值(V1,V2,...,VN)和总和S.找到其总和为S的最小硬币数量(我们可以使用一种类型的硬币.我们想要),或者报告说不可能以这样的方式选择硬币,它们总结为S.

我试着理解动态编程,还没弄明白.我不明白给出的解释,所以也许你可以给我一些提示如何编程这个任务？没有代码,只是我应该开始的想法.

谢谢.

我试图找到解决以下问题的最佳方法.最好的方式我的意思是不那么复杂.

作为输入,元组列表(开始,长度)如下:

[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]

每个元素通过其开始和长度来表示序列,例如(5,7)等同于序列(5,6,7,8,9,10,11)- 以5开头的7个元素的列表.可以假设元组按start元素排序.

输出应返回表示最长连续序列的非重叠元组组合.这意味着,解决方案是范围的子集,没有重叠且没有间隙,并且是最长的 - 尽管可能不止一个.

例如,对于给定的输入,解决方案是:

[(0,5),(5,7)] 相当于 (0,1,2,3,4,5,6,7,8,9,10,11)

它是回溯解决这个问题的最佳方法吗？

我对人们可以建议的任何不同方法感兴趣.

此外,如果有人知道这个问题的正式参考或另一个类似的问题,我想得到参考.

顺便说一句 - 这不是功课.

编辑

为了避免一些错误,这是预期行为的另一个例子

对于[(0,1),(1,7),(3,20),(8,5)]正确答案的输入[(3,20)]相当于(3,4,5,...,22)长度为20.收到的一些答案[(0,1),(1,7),(8,5)]相当于(0,1,2,...,11,12)作为正确答案.但这最后的答案是不正确的,因为它比短于[(3,20)].

在一个背包的情况下,用于最佳地填充背包的动态编程算法很好地工作.但是,是否有一种有效的已知算法可以最佳地填充2个背包(容量可能不相等)？

我尝试了以下两种方法,但它们都不正确.

1. 首先使用原始DP算法填充第一个背包,填充一个背包,然后填充另一个背包.
2. 首先填充尺寸为W1 + W2的背包,然后将溶液分成两个溶液(其中W1和W2是两个背包的容量).

问题陈述(另见维基百科的背包问题):

1. 我们必须用一组物品(每个物品具有重量和值)填充背包,以便最大化我们可以从物品获得的值,同时总重量小于或等于背包尺寸.

2. 我们不能多次使用一个项目.

3. 我们不能使用项目的一部分.我们不能把一个项目的一小部分.(每个项目必须完全包含或不包括在内).

我正在寻找一个很好的解决变更问题的方法,我找到了这个代码(Python):

target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
for coin in coins:
    for i in range(coin,target+1):
        ways[i]+=ways[i-coin]
print(ways[target])

我理解代码的字面意思是没有问题,但我无法理解为什么它有效.有人可以帮忙吗？

给定大小为n的数组,对于从1到n的每个k,找到大小为k的连续子阵列的最大和.

这个问题有一个明显的解决方案,时间复杂度为O(N ²)和O(1)空间.Lua代码:

array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
n = #array

function maxArray(k)
    ksum = 0
    for i = 1, k do
        ksum = ksum + array[i]
    end
    max_ksum = ksum
    for i = k + 1, n do
        add_index = i
        sub_index = i - k
        ksum = ksum + array[add_index] - array[sub_index]
        max_ksum = math.max(ksum, max_ksum)
    end
    return max_ksum
end

for k = 1, n do
    print(k, maxArray(k))
end …

任何人都可以帮助我理解http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493中提到的问题解决方案背后的核心逻辑

锯齿形序列是交替增加和减少的序列.所以,1 3 2是锯齿形,但1 2 3不是.任何一个或两个元素的序列都是锯齿形.我们需要找到给定序列中最长的锯齿形子序列.子序列意味着元素不必是连续的,就像最长的子序列问题一样.因此,1 3 5 4 2可以具有1 5 4作为之字形子序列.我们对最长的一个感兴趣.

我知道这是一个动态编程问题,它与如何使用动态编程确定增长最快的子序列非常相似？.

我认为任何解决方案都需要一个外循环来迭代不同长度的序列,内循环必须迭代所有序列.

我们将在索引i处存储最长的zig zag序列存储在另一个数组中,比如在索引i处的dpStore.因此,存储中间结果,以后可以重复使用.这部分是所有动态编程问题的共同点.稍后我们找到全局最大值并返回它.

我的解决方案绝对是错误的,粘贴在这里以显示我到目前为止的情况.我想知道我哪里出错了.

    private int isZigzag(int[] arr)
{
    int max=0;
    int maxLength=-100;
    int[] dpStore = new int[arr.length];

    dpStore[0]=1;

    if(arr.length==1)
    {
        return 1;
    }
    else if(arr.length==2)
    {
        return 2;
    }
    else 
    {           
        for(int i=3; i<arr.length;i++)
        {
            maxLength=-100;
            for(int j=1;j<i && j+1<=arr.length; j++)
            {
                if(( arr[j]>arr[j-1] && arr[j]>arr[j+1])
                    ||(arr[j]<arr[j-1] && arr[j]<arr[j+1]))
                {
                    maxLength = Math.max(dpStore[j]+1, maxLength);
                }
            }
            dpStore[i]=maxLength;               
        }
    }
    max=-1000; …

我正在努力有效地解决SPOJ问题64:排列.

设A = [a1,a2,...,an]是整数1,2,...,n的排列.如果ai> aj,则一对索引(i,j),1 <= i <= j <= n,是置换A的反转.我们给出整数n> 0和k> = 0.包含正好k次反转的n元素排列的数量是多少？

例如,恰好1次反转的4元素排列的数量等于3.

为了使给定的示例更容易看到,这里有三个4元素排列,正好有1个反转:

(1, 2, 4, 3)
(1, 3, 2, 4)
(2, 1, 3, 4)

在第一个排列中,4> 3且指数4小于3的指数.这是单个反转.由于置换只有一次反转,因此它是我们试图计算的排列之一.

对于任何给定的n个元素序列,排列的数量是阶乘(n).因此,如果我使用强力n ²方法计算每个排列的反转次数,然后检查它们是否等于k,则该问题的解决方案将具有时间复杂度O(n!*n ²).

以前的研究

这个问题的一个子问题以前问这里在计算器上.给出了使用合并排序的O(n log n)解决方案,其计算单个排列中的反转次数.但是,如果我使用该解决方案来计算每个排列的反转次数,我仍然会得到O(n!*n log n)的时间复杂度,在我看来这仍然很高.

之前在Stack Overflow上也提到了这个确切的问题,但它没有收到任何答案.

如果没有数学公式来解决这个问题(我有点怀疑),那么我也看到人们提示有效的动态编程解决方案是可能的.使用DP或其他方法,我真的想制定一个比O(n!*n log n)更有效的解决方案,但我不确定从哪里开始.

欢迎任何提示,评论或建议.

编辑:我已经用DP方法回答了下面的问题来计算Mahonian数.

几年前我参加了算法课程,我们给出了以下问题(或类似的问题):

有一个n楼层的楼层,电梯一次只能上2层楼,一次只能下3层楼.使用动态编程编写一个函数,该函数将计算电梯从一层i到另一层所需的步数j.

使用有状态方法显然很容易,你创建一个数组n个元素,并用值填充它.你甚至可以使用一种技术上非有状态的方法,它涉及累积结果递归传递它.我的问题是如何通过使用延迟评估和打结来以非有状态的方式执行此操作.

我想我已经设计了正确的数学公式:

where i+2和i-3是否在允许的值范围内.

不幸的是我不能让它终止.如果我i+2首先放置案例然后选择一个偶数楼层,我可以让它来评估目标等级以下的均匀楼层,但就是这样.我怀疑它直接射向最高的平坦地板,其他一切,下降3级,然后重复,永远在最顶层的几层之间振荡.

所以它可能以深度优先的方式探索无限空间(或有限但有环).我无法想象如何以广泛的方式探索这个空间而不使用其间有效模仿状态方法的大量数据结构.

虽然这个简单的问题令人失望,但我怀疑在一维中看到了一个解决方案,我可能能够使它适用于问题的二维变化.

编辑:许多答案试图以不同的方式解决问题.问题本身对我来说并不感兴趣,问题在于使用的方法.Chaosmatter创建一个minimal可以比较潜在无限数字的函数的方法可能是朝着正确方向迈出的一步.不幸的是,如果我尝试创建一个表示100层楼的列表,结果计算时间太长,因为子问题的解决方案不会被重用.

我尝试使用自引用数据结构,但它没有终止,存在某种无限循环.我会发布我的代码,这样你就可以理解我的目标.如果有人能够在自引用数据结构上使用动态编程实际解决问题,我会改变接受的答案,使用懒惰来避免多次计算事物.

levels = go [0..10]
  where
    go [] = []
    go (x:xs) = minimum
      [ if i == 7
          then 0
          else 1 + levels !! i
        | i <- filter (\n -> n >= 0 && n <= 10) [x+2,x-3] ]
      : go xs

您可以看到如何1 + levels !! i尝试引用先前计算的结果以及如何filter (\n -> n >= …

UPD.我解决了这个问题.

让我们访问城市DP[i][vertex_a][vertex_b]的州i和两个站在顶点的玩家vertex_a, vertex_b(保证其中一个站在那里list[i]).WLOG假设vertex_a ? vertex_b该DP表不包含有关球员位置的信息.只有三种状态可以达到DP[i][vertex_a][vertex_b],即DP[i + 1][vertex_a][vertex_b],DP[i + 1][list[i]][vertex_b],DP[i + 1][vertex_a][list[i]].我们还只需要存储两层DP,因此只sizeof(int) * 2 * 200 * 200需要计算最佳路径成本所需的字节数.为了获得路径,将last_move_id[i][vertex_a][vertex_b]携带关于在状态下移动的玩家的信息DP[i][vertex_a][vertex_b]并last_move_positions[i][vertex_a][vertex_b]存储玩家到达的顶点的数量list[i].由于顶点数不超过200,因此将其存储为as byte,因此sizeof(byte) * 1000 * 200 * 200每个数组都有字节.为了维护这些数组,必须有另一个数组,其中包含positions[i][vertex_a][vertex_b][3]有关每个播放器位置的信息,只需要最后两层,因此需要sizeof(byte) * 2 * 200 * 200 * 3这个字节.时间复杂O(N * L * L).

我的C++ …