标签: dynamic-programming

我试图找到3个或更多字符串的最长公共子序列.维基百科的文章很好地描述了如何为2个字符串执行此操作,但我不太确定如何将其扩展为3个或更多字符串.

有很多库可以找到2个字符串的LCS,所以我想尽可能使用其中一个.如果我有3个字符串A,B和C,找到A和B的LCS作为X是有效的,然后找到X和C的LCS,或者这是错误的方法吗？

我在Python中实现了如下:

import difflib

def lcs(str1, str2):
    sm = difflib.SequenceMatcher()
    sm.set_seqs(str1, str2)
    matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
    return "".join(matching_blocks)

print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])

这输出"ba",但它应该是"baa".

我在接受采访时遇到了以下问题:

给定一个有N个台阶的楼梯,每次可以进行1步或2步.输出从下到上的所有可能方式.

例如:

N = 3

Output :
1 1 1
1 2
2 1

在面试时,我只是说使用动态编程.

S(n)= S(n-1)+1或S(n)= S(n-1)+2

但是,在采访中,我没有为此编写非常好的代码.你会如何编写这个问题的解决方案？

谢谢!

我在一次采访中向我询问了这个问题,并且令人尴尬地暴露了我在动态编程方面的缺点.如果有人可以帮我解决这个问题,我将不胜感激.此外,如果您能够在设计解决方案时解释您的思维过程对我(以及其他人)非常有帮助,因为当我看到一个使用动态编程范例的解决方案但我很难理解时,我似乎能够理解跟我一起.

不用多说,这是我被问到的问题.

给定一个整数i,并设置X的k点x1,x2,... xk上实线,选择i从设定点X,以尽量减少对距离的每一个点的总和X到一个点在i使用动态规划.

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
   (a) max_ending_here = max_ending_here + a[i]
   (b) if(max_ending_here < 0)
         max_ending_here = 0
   (c) if(max_so_far < max_ending_here)
          max_so_far = max_ending_here
 return max_so_far

我可以帮助我理解上述算法中最佳的子结构和重叠问题(DP的面包和黄油)吗？

更新

在更多阅读之后,可以给出具有以下递归关系的解决方案:

(a) When i = 1 and j = 2, l(i; j) = dist(pi; pj )
(b) When i < j - 1; l(i; j) = l(i; j - 1) + dist(pj-1; pj)
(c) When i = j - 1 and j > 2, min 1<=k<i (l(k; i) + dist(pk; pj ))

现在开始有意义了,除了C部分.我如何确定最小值k？我想这意味着你可以迭代所有可能的k值并只存储(l(k,i)+ dist(pk,pj)的最小结果？

是的,绝对是我在学校学习的一个问题.我们正在研究旅行商问题的比特旅游.

不管怎么说,我有5个顶点{0,1,2,3,4}.我知道我的第一步是按照增加x坐标的顺序对它们进行排序.从那里开始,我对动态编程如何完成这一点感到困惑.

我正在阅读我应该扫描已排序节点的列表,并维护两个部分(初始路径和返回路径)的最佳路径.我对如何计算这些最佳路径感到困惑.例如,我如何知道是否应该在初始路径或返回路径中包含给定节点,因为它不能同时包含(两个端点除外).回想一下斐波纳契的动态编程,你基本上从基础案例入手,继续前进.我想我要问的是如何开始使用比特型旅行推销员问题？

对于类似Fibonacci数字的东西,接近的动态编程非常清楚.但是,我不知道我是不是只是在密集或什么,但我很困惑试图绕过这个问题.

谢谢你的期待!

注意:我不是在寻找完整的解决方案,但至少有一些很好的技巧可以让我开始.例如,如果这是Fibonacci问题,可以说明如何计算前几个数字.请告诉我如何改进这个问题.

我正在审查算法课程中的一些旧笔记,动态编程问题对我来说似乎有点棘手.我有一个问题,我们有无限量的硬币,有一些面额x1,x2,... xn我们想要改变一些价值X.我们正在设计一个动态程序来决定是否可以改变X是否制造(不是最小化硬币数量,或返回哪些硬币,只是真或假).

我已经做了一些关于这个问题的思考,我可以看到这样做的递归方法,就像它...

MakeChange(X, x[1..n this is the coins])
    for (int i = 1; i < n; i++)
    {
        if ( (X - x[i] ==0) || MakeChange(X - x[i]) )
            return true;
    }
    return false;

转换这个动态程序对我来说并不容易.我怎么能接近这个？

以下是将字符串转换为具有最少操作数的回文结构的问题状态.我知道它与Levenshtein距离类似 但我还不能解决它

例如,对于输入mohammadsajjadhossain,输出是8.

我正在尝试提出一种动态编程算法,该算法在矩阵中找到由相同数字组成的最大子矩阵:

例:

{5 5 8}
{5 5 7}
{3 4 1}

答案:由于矩阵导致4个元素

   5 5 
   5 5   

我知道使用自下而上动态编程方法的解决方案在O(n ^ 2)中解决了这个问题.我特意寻找自上而下的dp方法.是否有可能使用递归解决方案实现最长的回文子串？

这是我尝试过的但是在某些情况下它失败了,但我觉得我差不多正常.

#include <iostream>
#include <string>

using namespace std;

string S;
int dp[55][55];

int solve(int x,int y,int val)
{

    if(x>y)return val;
    int &ret = dp[x][y];
    if(ret!=0){ret = val + ret;return ret;}
    //cout<<"x: "<<x<<" y: "<<y<<" val: "<<val<<endl;
    if(S[x] == S[y])
        ret = solve(x+1,y-1,val+2 - (x==y));
    else
        ret = max(solve(x+1,y,0),solve(x,y-1,0));
    return ret;
}


int main()
{
    cin >> S;
    memset(dp,0,sizeof(dp));
    int num = solve(0,S.size()-1,0);
    cout<<num<<endl;
}

我已经浏览了网站上的各种问题,我没有设法通过以下推理找到任何实现这一点的东西(所以我希望这不是重复).

我试图通过C程序解决的问题如下:

作为自动售货机控制器的程序员,您需要计算构成所需更改的最小硬币数量,以便回馈给客户.这个问题的有效解决方案采用动态编程方法,首先计算1美分变化所需的硬币数量,然后计算2美分,然后计算3美分,直到达到所需的变化,每次使用先前的计算硬币数量.编写一个包含该功能的程序,该程序ComputeChange()获取有效硬币列表和所需的更改.该程序应反复询问控制台所需的更改并进行相应的调用ComputeChange().它还应该使用"缓存",其中保留任何先前计算的中间值以用于后续查找.

在网上四处寻找其他人如何解决它后,我发现下面的例子应用了便士,镍币和硬币:

我尝试以我的代码为基础.但首先,我的代码没有停止,其次,我不确定我是否合并了上面的标题中提到的缓存元素.(我不确定我需要去做那个部分).

任何人都可以帮我找到代码中的缺陷吗？

#include <stdio.h>
#include <limits.h>

int computeChange(int[],int,int);
int min(int[],int);

int main(){
    int cur[]={1,2,5,10,20,50,100,200};
    int n = sizeof(cur)/sizeof(int);
    int v;

    printf("Enter a value in euro cents: ");
    scanf("%d", &v);

    printf("The minimum number of euro coins required is %d", computeChange(cur, v, n));

    return 0;
}

int computeChange(int cur[], int v, int n){
    if(v < 0)
        return -1;
    else if(v == 0)
        return 0;
    else{
        int possible_mins[n], i;
        for(i = 0; i …