标签: dynamic-programming

我试图解决Cormem的算法导论第3版(第405页)中的动态编程问题,该问题如下:

回文是一些字母表上的非空字符串,它向前和向后读取相同的字符串.回文的实例是长度为1的所有字符串,civic,racecar,和aibohphobia (回文的恐惧).

给出一个有效的算法来找到作为给定输入字符串的子序列的最长回文.例如,给定输入 character,您的算法应该返回carac.

好吧,我可以通过两种方式解决它:

第一解决方案

字符串的最长回文子序列(LPS)只是其自身及其反向的最长公共子序列.(我在解决了另一个要求序列的最长增加子序列的相关问题后构建了这个解决方案).由于它只是一个LCS变体,它还需要O(n²)时间和O(n²)存储器.

二解决方案:

第二个解决方案稍微详细一点,但也遵循一般的LCS模板.它来自以下重现:

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

用于计算lps长度的伪代码如下:

compute-lps(s, n):

    // palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    // palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    // …

来自LeetCode

给定字符串S和字符串T,计算S中T的不同子序列的数量.

字符串的子序列是一个新字符串,它是通过删除一些(可以是无)字符而不干扰其余字符的相对位置而由原始字符串形成的.(即,"ACE"是"ABCDE"的子序列,而"AEC"不是).

这是一个例子:S ="rabbbit",T ="rabbit"

返回3.

我看到一个非常好的DP解决方案,但是,我很难理解它,任何人都可以解释这个dp是如何工作的？

int numDistinct(string S, string T) {

    vector<int> f(T.size()+1);

    //set the last size to 1.
    f[T.size()]=1;

    for(int i=S.size()-1; i>=0; --i){
        for(int j=0; j<T.size(); ++j){
            f[j]+=(S[i]==T[j])*f[j+1];
            printf("%d\t", f[j] );
        }
        cout<<"\n";
    }
    return f[0];
}

这是一个基于俄罗斯方块的谜题.在这个谜题中,我们将获得接下来将从顶部落下的n个片段的序列.我们的工作是在GameOver之前最大化得分.一般的俄罗斯方块没有多项式时间算法,但在这个难题中只允许I(直)四联体.虽然它不允许旋转它们.

所以这里是约束:

• 该板是W×H矩形
• 我们给出了下n个四联骨牌的序列
• 只允许我使用tetromino(水平或垂直)
• 不允许旋转
• 当行填满时,行会被清除
• 董事会最初是空的
• 每行清除1分.
• 当tetrominoes叠加到比赛场地的顶部时,游戏结束了.

找到可以获得的最高分数.

例:

8 x 6板.接下来的7个tetrominoes是[——,|,|,——,|,——,|]其中'——'表示水平我四氨基和|表示垂直我四氨基.

在这种情况下,最大可能得分是3使用以下策略('.'代表空板,'#'代表四氨基片的一部分).

Initially:
........
........
........
........
........
........
1st move:
........
........
........
........
........
####....
2nd Move:
........
........
.......#
.......#
.......#
####...#
3rd Move:
........
........
......##
......##
......##
####..##
4th Move:
........
........
......##
......##
####..##
####..##
5th Move:
........
........
.....###
.....###
####.###
####.###
6th Move:
........
........
.....### …

如何计算3长度k < n数组中长度(或一般长度)的不同子序列的数量n？

注意:如果两个子序列中的元素顺序不同,则认为它们是不同的.

例如:假设数组A = [1, 2, 1, 1],那么答案应该是3因为长度只有三个不同的子序列,3如下所示:

[1, 1, 1]
[1, 2, 1]
[2, 1, 1]

数组的大小,数组n <= 10^5中的每个元素A_i <= n.

我的方法:

我想到了蛮力方法,即采用长度元组3并将其插入地图中.但这不是空间/时间效率.

编辑:这是一个采访问题,它说,对于k = 3,预期的时间和空间复杂度是O(n).

给定一组 NXP 堆栈，其中 N 是堆栈数，P 是堆栈容量，如何计算从位置 A 的某个节点移动到某个任意位置 B 所需的最小交换次数？我正在设计一个游戏，最终目标是对所有堆栈进行排序，使它们都具有相同的颜色。

# Let "-" represent blank spaces, and assume the stacks are
stacks = [
           ['R', 'R', 'R', 'R'], 
           ['Y', 'Y', 'Y', 'Y'], 
           ['G', 'G', 'G', 'G'], 
           ['-', '-', '-', 'B'], 
           ['-', 'B', 'B', 'B']
         ]

如果我想在stacks[1][1]这样的stacks[1] = ["-", "B", "Y", "Y"]. 我如何确定这样做所需的最小移动次数？

我一直在研究多种方法，我尝试过从一个状态生成所有可能的移动的遗传算法，对它们进行评分，然后继续沿着最佳评分路径，我还尝试运行 Djikstra 的算法来寻找问题的路径. 这看起来简单得令人沮丧，但我想不出办法让它在指数时间内运行。是否有我遗漏的适用于此的算法？

编辑

我编写了这个函数来计算所需的最小移动次数： stacks: List of Characters List of Characters 代表堆栈中的碎片，stacks[0][0] 是 stack[0] 的顶部 stack_ind：将被添加到堆栈的碎片needs_piece：应该被添加到堆栈的碎片needs_index：碎片应该位于的索引

def calculate_min_moves(stacks, stack_ind, needs_piece, needs_index):
    # …

例如,如果我有一个列表

[1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]

该算法应返回[1,2,3,4,5,6,7,8,9,10,11].

澄清一下,最长的清单应该向前运行.我想知道什么是算法上有效的方法(最好不是O(n ^ 2))？

此外,我对一个不在python中的解决方案持开放态度,因为算法才是最重要的.

谢谢.

我正在尝试解决以下DP问题:

您有4种类型的乐高积木,尺寸为1*1*1,1*1*2,1*1*3和1*1*4.假设您拥有无限数量的每种类型的积木.

你想在这些块中制作一个高度为H和宽度为M的墙.墙上不应有任何孔.你建造的墙应该是一个坚固的结构.坚固的结构意味着不应该沿着任何垂直线分开墙壁而不切割用于建造墙壁的任何乐高积木.块只能水平放置.墙可以建造多少种方式？

以下是我的尝试方法:用abcd表示1*1*1,1*1*2,1*1*3和1*1*4块.有效模式以粗体表示.无效模式可以被垂直线打破.

H = 1&W = 3 #valid pattern = 1
aa ab ba c

H = 2&W = 3 #valid pattern = 9

我试图通过高度或宽度来找到递推模式,以找到H = 3&W = 3或H = 2&W = 4的值.

关于如何通过身高或体重来计算增长的任何输入？
PS墙壁总是H*W*1.

我一直想知道这件事.没有书明确说明这一点.

回溯正在探索所有可能性,直到我们发现一种可能性无法引导我们找到可能的解决方案,在这种情况下我们放弃它.

据我所知,动态编程的特点是重叠的子问题.那么,动态编程是否可以表示为缓存回溯(对于以前探索过的路径)？

谢谢

我在一次采访中遇到了这个问题而无法理解.我相信它有一个动态的编程解决方案,但它让我望而却步.

给定一些砖块,输出可能的2d金字塔总数,其中金字塔被定义为任何结构,其中一排砖块的砖块严重少于其下方的砖块.你不必使用所有砖块.

砖块只是一个正方形,连续砖块的数量是唯一重要的信息.

真的坚持这个,我认为很容易解决每个问题1 ... n迭代和总和.但是提出金字塔的数量可能与我的砖块正在躲避我.

例如,n = 6

X

XX

X
XX   XXX

X
XXX   XXXX

XX      X
XXX   XXXX   XXXXX

X
XX      XX       X
XXX   XXXX   XXXXX   XXXXXX

所以答案是来自6块砖的13个可能的金字塔.

编辑

我很肯定这是一个动态编程问题,因为(一旦你确定了第一行)它只是查看你剩余砖块的记忆数组中的索引,看看有多少金字塔适合于顶部.

这也是情理之中的考虑宽度至少n/2的底部行,因为我们没有更多的砖上面比下面一行EXCEPT,这是我失去它,我的脑海里分崩离析,在某些(少数情况下)你可以N = 10

X
XX
XXX
XXXX

现在底行有4个,但最左边有6个

但是当n = 11时,我们不能有低于n/2砖的底行.还有另外一种奇怪的不一致性,如n = 4,我们不能有一排n/2 = 2砖.

优化O(n^2)算法O(n log n).

问题陈述

考虑到阵列A的n正整数.将数组划分为长度不大于连续子序列,k使得每个子序列的最大值之和最小.这是一个例子.

如果n = 8和,k = 5和数组的元素1 4 1 3 4 7 2 2,最好的解决方案是1 | 4 1 3 4 7 | 2 2.总和将是max{1} + max{4, 1, 3, 4, 7} + max{2, 2} = 1 + 7 + 2 = 10.

O(n ^ 2)解

我们dp[i]是最低金额为问题语句子问题阵列A[0] ... A[i].dp[0] = A[0]而且,对于0 < i …