精华内容
下载资源
问答
  • 备忘录算法

    2014-03-22 15:51:42
    这是一个用C++做备忘录算法,备忘录方法是动态规划方法的变形。与动态规划算法不同的是,备忘录方法的递归方式是顶向下的,而动态规划算法则是自底向上
  • # ------------------------------------自底向上----------------------------------- def LCS_DowntoUp(X, Y): m = len(X) n = len(Y) c, b = [], [] for i in range(m + 1): c.append([0 for i in range(n +...

    一、计算LCS的长度

    LCS(longest-common-subsequence problem)就是两个序列中最长的公共子序列

    例如:X1=[1,2,3,4,5,6,76,66]   X2=[2,453,3,545,4,4324]   在这两段序列中LCS 为2,3,4

    定理:LCS最优子结构:

    令X=[x1,x2,x3,x4,.......,xm]    Y=[y1,y2,y3,y4,.........,ym]   Z=[z1,z2,z3,z4......,zk]是X,Y的任意LCS

    1.如果xm==yn,就是说最后两个相同时,对于两个序列来说,可以暂时把分别位于最后的这两个xm and yn拿出来,由原来的找X[x1~xm]和Y[y1~yn]的LCS变为找X[x1~x(m-1)]和Y[y1~y(n-1)]的LCS。由于xm=yn,所以可以原问题比子问题的LCS多1

    2.如果xm!=yn,并且如果zk!=xm则说明Z是X(m-1)和Y的一个LCS,因为LCS的最后一个不是X的最后一个,那把X中的最后一个去了也无妨喽;同理zk!=yn则说明Z是X和Y(n-1)的一个LCS。所以找到这两种情况下最长的就行了。

    #备注代码中c是存放的是XiYjLCS长度

    i和j是分别在X和Y序列的下标,从右到左.在代码中,ij不是字符串的下标,而是下标加1,也就是说ij是子串长度

    b存放的东西是构造LCS需要用的

    # ------------------------------------备忘录实现-----------------------------------
    def LCS(X, Y):
        m, n = len(X), len(Y)
        c = []
        b = []
        for i in range(m + 1):
            c.append([float('inf') for i in range(n + 1)])
            b.append([float('inf') for i in range(n + 1)])
        LCS_help(X, Y, c, b)
        for i in range(len(X) + 1):
            print(c[i])
        print("----------------------------------")
        for i in range(len(X) + 1):
            print(b[i])
        Print_LCS(b, X, len(X), len(Y))
        # print(c)
    def LCS_help(X, Y, c, b):
        i = len(X)
        j = len(Y)
        if c[i][j] < float('inf'):
            return c[i][j]
        if i == 0 or j == 0:
            c[i][j] = 0
        elif X[i - 1] == Y[j - 1]:
            X1 = X[:i - 1]
            Y1 = Y[:j - 1]
            b[i][j]="LUP"
            c[i][j] = LCS_help(X1, Y1, c, b) + 1
        else:
            X1 = X[:i - 1]
            Y1 = Y[:j - 1]
            if(LCS_help(X1, Y, c, b)>=LCS_help(X, Y1, c, b)):
                b[i][j]="UP"
                c[i][j]=LCS_help(X1, Y, c, b)
            else:
                b[i][j] = "L"
                c[i][j] = LCS_help(X, Y1, c, b)
            #c[i][j] = max(LCS_help(X, Y1, c, b), LCS_help(X1, Y, c, b))
        return c[i][j]
    
    # ------------------------------------自底向上-----------------------------------
    def LCS_DowntoUp(X, Y):
        m = len(X)
        n = len(Y)
        c, b = [], []
        for i in range(m + 1):
            c.append([0 for i in range(n + 1)])
            b.append([0 for i in range(n + 1)])
        for i in range(0, m + 1):
            c[i][0] = 0
        for j in range(0, n + 1):
            c[0][j] = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if (X[i - 1] == Y[j - 1]):
                    c[i][j] = c[i - 1][j - 1] + 1
                    b[i][j] = "LUP"
                elif (c[i-1][j] >= c[i][j - 1]):
                    c[i][j] = c[i - 1][j]
                    b[i][j] = "UP"
                else:
                    c[i][j] = c[i][j - 1]
                    b[i][j] = "L"
        for i in range(len(X) + 1):
            print(c[i])
    
        print("----------------------------------")
        for i in range(len(X) + 1):
            print(b[i])
        Print_LCS(b,X,len(X),len(Y))
        return c, b

    二,LCS的构造

    def Print_LCS(b,X,i,j):
        if i==0 or j==0:
            return
        if b[i][j]=="LUP":
            Print_LCS(b,X,i-1,j-1)
            print(X[i-1])
        elif b[i][j]=="UP":
            Print_LCS(b,X,i-1,j)
        else:
            Print_LCS(b,X,i,j-1)

    我们可以这样理解,从LCS的最优解定理出发来思考:

    #在构造的b中储存了字符串“LUP”"UP"“L”,分别表示左上,正上,左。b的横坐标看成Y的length,纵坐标是X的length

    ex:

    NONEy1y2y3y4y5y6
    x1      
    x2      
    x3      
    x4     LUP↖

    假如末尾两个字符相同,那么这时候算X(m-1)和Y(n-1),所以可以同时将XY减少一个,即左上方的小框框

    假如末尾不同则考虑两种不同情况,比较分别各去除最后一个字符的子问题的解。假如X去了一个的情况下比较大所以选择X去了最后一个的情况,那么向上一格;同理,Y去一个比较大那么向左。

    (小补充:)

    在构造LCS的函数中,根据上述情况进行递归,直到i==0 or j==0;即子串长度是0的时候递归截止。并且仅在字符相同的时候打印,递归由上到下进行,虽然先遇到字符串较长时候的相同字符,但是调用递归表达式,然后在输出,导致输出的结果就是正着方向的了。

    展开全文
  • 在我们的课程设计、大作业中会涉及到挖金矿问题,今天我用备忘录算法解决,可以得到最优解,便于帮助你们。 //有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。 //参与挖矿工人的...

    挖金矿问题-动态规划-备忘录算法(最优解)

    在我们的课程设计、大作业中会涉及到挖金矿问题,今天我用备忘录算法解决,可以得到最优解,便于帮助你们。
    在这里插入图片描述
    //有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。
    //参与挖矿工人的总数是10人。
    //每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。
    //要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?
    /*
    500金/5人 200/3 300/4 350/3 400/5
    /
    /

    总容量:10人
    可选量:5人
    n=10,c=5;
    表前i座金山占用j人所拥有的最大黄金
    状态转移方程
    1.j>wi
    F(i,j)=F(i-1,j);
    2.j<=wi
    F(i,j)=max(F(i-1,j),F(i-1,j-wi)+vi);
    */

    在这里插入代码片
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    typedef struct node{
     int w;
     int v;
    } Node;
    Node Moun[6];
    Node Orign[6];
    int c=10,n=5;
    bool cmp(Node a,Node b){
     if(a.v==b.v)
      return a.w<b.w;
     return a.v>b.v;
    }
    void copy(){
     for(int i=1;i<=n;i++){
      Orign[i].w=Moun[i].w;
      Orign[i].v=Moun[i].v;
     }
    }
    int main(){
     int F[6][11];//备忘录
     int book[6];//标记选取的金山
     int w[6],v[6];
     //初始化
     memset(F,0,sizeof(F));
     memset(book,0,sizeof(book));
     //存入数据 500金/5人    200/3 300/4 350/3 400/5
     Moun[1].v=500,Moun[1].w=5;
     Moun[2].v=200,Moun[2].w=3;
     Moun[3].v=300,Moun[3].w=4;
     Moun[4].v=350,Moun[4].w=3;
     Moun[5].v=400,Moun[5].w=5;
     //复制原金山位置,方便以后求最优解
     copy();
     //按比率排序
     sort(Moun+1,Moun+n+1,cmp);
     //自底向上更新备忘录,找最优值
     for(int i=1;i<=n;i++){
      for(int j=1;j<=c;j++){
       if(Moun[i].w<=j){
        F[i][j]=max(F[i-1][j],F[i-1][j-Moun[i].w]+Moun[i].v);
       }else{
        F[i][j]=F[i-1][j];
       }
      }
     }
     //自顶向下 求最优解
     int tmp=10;
     int k=0;
     for(int i=n;i>=1;i--){
      if(F[i][tmp]!=F[i-1][tmp]){//不相同说明放入
       book[k++]=i; 
      }else{
       tmp-=Orign[i].w;
      }
     }
     //输出最优质值
     cout<<"输出最优质值:"<<endl;
     cout<<F[5][10]<<endl;
     //输出最优解
     cout<<"输出最优解:"<<endl;
     for(int i=0;i<k;i++){
      cout<<"第"<<book[i]<<"座金山"<<endl;
     }
     return 0;
    }
    

    结果:

    输出最优质值:
    900
    输出最优解:
    第2座金山
    第1座金山

    希望可以帮助到你们!

    展开全文
  • 动态规划有两种等价实现方法:带备忘顶向下发(topDownWithMemoization),自底向上方法,付出额外的内存空间来节省计算时间,是典型的时空权衡,递归时会保存每个子问题的解 长度n与对应价格p关系 1~10...

    本博文资料来源于算法导论第三版

    动态规划有两种等价实现方法:带备忘的自顶向下发(topDownWithMemoization),自底向上方法,付出额外的内存空间来节省计算时间,是典型的时空权衡,递归时会保存每个子问题的解



    长度n与对应价格p关系



    1~10的对应最优收益



    朴素递归之自顶向下方法伪代码



    c++代码

    #include <iostream>
    
    using namespace std;
    
    upDownCutRod(int p[],int n)
    {
        if(n==0)
            return 0;
        int q=-1;
        for(int i=0;i<n;++i)
            q=max(q,p[i]+upDownCutRod(p,n-i-1));
        return q;
    }
    
    int main()
    {
        int p[10]={1,5,8,9,10,17,17,20,24,30};
        int q=upDownCutRod(p,10);
        cout<<"最优收益值为:"<<q;
        return 0;
    }
    

    运行结果



    动态规划自顶向下伪代码




    c++代码实现

    #include <iostream>
    
    using namespace std;
    
    int memorizedCutRodAux(int p[],int n,int r[])
    {
        int q;//最大收益值
        if(r[n]>=0)
            return r[n];//检查所需值是否已知
        if(n==0)
            q=0;//n=0时不会有收益
        else
        {
            q=-1;
            for(int i=0;i<n;++i)
                q=max(q,p[i]+memorizedCutRodAux(p,n-i-1,r));
        }
        r[n]=q;
        return q;
    }
    
    memorizedCutRod(int p[],int n)
    {
        int r[n+1];
        for(int i=0;i<=n;++i)
            r[i]=-1;
        return memorizedCutRodAux(p,n,r);
    }
    
    int main()
    {
        int p[10]={1,5,8,9,10,17,17,20,24,30};
        int q=memorizedCutRod(p,10);
        cout<<"带备忘的自顶向下方法的最优收益值为:"<<q;
        return 0;
    }
    

    运行结果



    自底向上方法伪代码



    c++代码实现

    #include <iostream>
    
    using namespace std;
    
    int bottomUpCutRod(int p[],int n)
    {
        int r[n+1];//记录不同规模子问题的解,这里是1~10
        int q;//记录收益
        r[0]=0;
        for(int j=1;j<=n;++j)
        {
            q=-1;//初始为负,常见的表示未知数的方法
            for(int i=1;i<=j;++i)
            {
                q=max(q,p[i-1]+r[j-i]);//不再使用递归
            }
            r[j]=q;
        }
        return r[n];
    }
    
    int main()
    {
        int p[10]={1,5,8,9,10,17,17,20,24,30};
        int q=bottomUpCutRod(p,10);
        cout<<"自底向上方法的最优收益值为:"<<q;
        return 0;
    }
    

    运行结果




    展开全文
  • 备忘录实际上也是从上往下进行递归求解,只是每次都将求解的值记录下来,避免了大量的重复计算。 我的伪代码如下: 在直接递归法的基础上,只在代码的最后面加上return c[i][j],作为每一次递归调用的返回值。...

    问题定义:

    最长公共子序列:给定两个序列X={x1,x2,……xn},Y={y1,y2……,ym},如果X的子序列存在一个严格递增的下标序列{,,……},使得对于所有的j=1,2……,k,有=,则称产生的数组为对应的公共子序列。

    如果公共子序列的长度最大,我们就称之为最长公共子序列,并求出LCS的长度(最优值)和对应的子序列(最优解)。

    我们将和所对应的长度存储在数组里,并记录为c[i][j]。

    我们可以证明问题的求解具有:

    1.最优子结构性质。 问题的最优解包括子问题的最优解,不同子问题的最优解叠加在一起就是总问题的最优解

    2.和重叠子问题:子问题有多个且具有重复性,如果两个序列不存在任何相同的元素,则c[1][1]=c[m][n]。

     

    基于以上两点性质,可以用动态规划的算法来进行求解。顺便一提,在ACM题目中有很多这样的题,任何求序列问题(如MaxSum)和树的问题(如二叉搜索树),几乎不用证明就可以去求解。

    直接给出公式:

     

     

    二 问题求解兼代码:

    在已经给出公式的前提下,以下为所进行的的四种方法:

    1.对穷举法: 我的思路是定义一个向量组Z,存储所有X元素存在的情况,|Z|=(2^n)*n,且Zn∈{0,1}。之后按照if(Zn,n∈1→n)的判断方式,每次都可以生成X的一个子序列,只要依次判断Y中是否存在公共子序列,存储并更新对应的长度,就能求出LCS的长度。但所耗费的时间复杂度太大。并且程序往往会卡住,运行不出来。


    2.对直接递归法:在公式已经给定的情况下,最简单的思考方式就是进行直接递归。

    我的伪代码如下:

    <span style="font-size:14px;">Int Lcs_length(int i,int j){
    If(i==0 || j==0) return 0;  //递归的边界条件
    Else if(x[i-1]==y[j-1]) return Lcs_length(i-1,j-1)+1;  //每一次都要进行新的递归
    Else return max(LCS_length(i,j-1),LCS_length(i-1,j)); }</span>

    直接递归法的缺点是显而易见的,每一次进行计算的时候都要重复计算。比如我拿(6,6)来进行举例,(6,6)第一次递归后的情况是(6,5)和(5,6),两者分别进行递归后又是(5,5)、(6,4)和(5,5)、(4,6),也就是说(5,5)被重复计算了两次。如果存在大量不相等元素的话,就会因此产生大量的冗余,影响运行效率。

    如果我们能够将每一次的结果(必要的)都保存下来,就可以节省大量的时间,因此导出了第三种方法。

     3.备忘录法:备忘录实际上也是从上往下进行递归求解,只是每次都将求解的值记录下来,避免了大量的重复计算。

    我的伪代码如下:

    在直接递归法的基础上,只在代码的最后面加上return c[i][j],作为每一次递归调用的返回值。

    其他情况下将return改为 c[i][j],记录在数组里即可。

    具体实现如图: 其中p[100]本来是要求具体的序列的,但实现起来发现几乎不可能。

        memset(c,-1,sizeof(c));
        strcpy(x,"ABCBDAB");
        strcpy(y,"BDCABA");
        int m=strlen(x),n=strlen(y);
        cout<<x<<endl;cout<<y<<endl;
     cout<<"the length:"<<Memorized_LCS(m,n)<<endl;
    
    count-=1;
    while(count--) cout<<p[count]<<endl;
            return 0;
    }
    
    int Memorized_LCS(int i,int j)
    {   memset(c,-1,sizeof(c));
        strcpy(x,"ABCBDAB");
        strcpy(y,"BDCABA");
        int m=strlen(x),n=strlen(y);
        cout<<x<<endl;cout<<y<<endl;
        if (c[i][j]>-1) return c[i][j]; //已经被计算过,就不用再次计算。
        if(i==0 || j==0) c[i][j]=0; //边界条件
        else if(x[i-1]==y[j-1])  {c[i][j]=Memorized_LCS(i-1,j-1)+1;p[count++]=x[i-1];}//因为不知道这次被调用的最终
        //最终是否会被纳入总的结果,因此可以认为是无法求出序列的
        else /*if(Memorized_LCS(i-1,j)> Memorized_LCS(i,j-1)) c[i][j]=Memorized_LCS(i-1,j);
            else c[i][j]=Memorized_LCS(i,j-1);*/
                 c[i][j]=max(Memorized_LCS(i,j-1),Memorized_LCS(i-1,j)); //max是自带的函数
        return c[i][j];
    
    }
    
    
    


    4.动态规划(DP)法:

    动态规划法的思想同样来源于直接递归法,只不过提前就将每次求解需要用到的c[i-1][j-1]都提前求好。记录下来。

    具体的求解过程如下所示:设两个子串的长度分别为n,m。则定义矩阵c[n+1][m+1],变化量从0到n,存储从子串x[1..n]和y[1..m]的子序列的长度。显然c[i][0]和c[0][j]都为0。

    接下来按照c[1][1..m],c[2][1..m],……c[n][1..m]的顺序自左向右来填每行的表。并且每一次递归时都记录下填表的方式,用1、2、3分别表示来自于c[i-1][j-1]、c[i-1][j]、c[i][j-1],这样在求出最优值的同时也能逆推出最优解。

    代码如下:

    #include<iostream>
    #include<cstring>
    using namespace std;
    #define max 1000
    
    int c[max][max];
    char x[100],y[100],z[100];
    int display[100][100];
    
    int fillform(int n,int m){
        //并没有进行递归调用
        memset(c,0,sizeof(c));
        memset(z,0,sizeof(z));
        memset(display,0,sizeof(display));
        int i,j,k;
    
    
        //先填行和纵列,之后再每行每列的填表
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++){
            if(x[i-1]==y[j-1]) {c[i][j]=c[i-1][j-1]+1;display[i][j]=1;}
        else if(c[i][j-1]>c[i-1][j]) {c[i][j]=c[i][j-1];display[i][j]=2;}
           else {c[i][j]=c[i-1][j];display[i][j]=3;} } //这时已经算出了所有的情况来
       cout<<"test:"<<c[3][3]<<c[n][m-1]<<endl;
         return c[n][m];
    }
    
    void show()
    {
    
        int n=strlen(x),m=strlen(y);
        int i,j,k;
    
        int count=0; //对应不同的作用
        while(n>0 && m>0) //不能是>=0
        {
            if(display[n][m]==1){
                z[count++]=x[n-1];n--;m--;}
                else if(display[n][m]==2) m--; //向上移动一层
                 else if(display[n][m]==3) n--; //向左移动一层
        }
    
        while(--count) cout<<z[count];cout<<z[0];
    }
    
    int main(void)
    {
       int count=5000;
       strcpy(x,"ABCBDAB");
        strcpy(y,"BDCABA");
    
       //cout<<x[1]<<y[1]<<endl;
        //cout<<strlen(x)<<" "<<strlen(y)<<endl;
        cout<<x<<endl;cout<<y<<endl;
             while(count--){
        cout<<"the length:"<<fillform(strlen(x),strlen(y))<<endl;}
        cout<<"the sequence:";show();
    
        return 0;
    }
    


     

    展开全文
  • 算法备忘录——排序

    千次阅读 2016-04-04 08:25:10
    排序是为了让查找更有效率。...前辈们排序算法研究已久,有些用直觉就能分析出来,即所谓基础排序,有些无法用直觉看出,还需要一些分析研究,即所谓高级排序。以下表格大致罗列一下主流的排序算法的特点。
  • 备忘录的递归 备忘录就是辅助数组,可以给庞大的递归树剪枝 带备忘录 的递归解法,相比暴力递归 复杂度 由O(2^n) 减少至 O(n) 暴力解法的复杂是由 重叠子问题 引起的, 计算 f(20) 需要知道 f(19) 和 f(18) 计算 f...
  • 算法备忘录——查找

    千次阅读 2016-08-21 22:41:03
    查找算法准确的说,应该是数据的组织方法与查找方法的结合。没有组织规律的数据,我们只能用直观的暴力方法,一个一个拿出来对比,从而筛选出待查找的元素。而一旦数据变得有组织有规律,查找就变得轻而易举了。
  •  “从左向右、从上向下、从右向左、从下向上” 四个方向循环 初始条件: 设置四个边界,l(left),r(right),t(top),b(bottom) int l = 0; //左边界 int r = matrix[0].size() - 1; //右边界 int t = 0; //上边界 ...
  • 备忘录方法

    2021-03-24 21:22:47
    与动态规划算法不同的是,备忘录方法的递归方式是顶向下的,而动态规划算法则是自底向上递归的。因此,备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备...
  • 使用备忘录方法解决0-1背包问题: 1.跟直接递归很相似,该算法能将递归遇到的子问题的解保存在一个表中,以便下一个递归遇到同样的子问题时快速求解。...3.备忘录算法与动态规划算法的区别有:
  • 转载:http://www.cnblogs.com/eniac12/p/5329396.html排序算法稳定性的简单...1.冒泡排序冒泡排序是一种极其简单的排序算法,也是我所学的第一个排序算法。它重复地走访过要排序的元素,依次比较相邻两个元素,如...
  • 常见算法知识备忘录1

    千次阅读 2011-03-21 17:20:00
    冒泡排序:程序见算法导论 P23 思想:最小的先冒起来 2.插入排序:思想:就像我们抓牌,插牌一样.在数列大部分有序的情况下比快排有效。最好情况O(n) 3.希尔排序: 思想见:数据结构课件DS07_Ch06a.pps第5页 4....
  • 与贪心算法试图通过局部最优解来组合成最优解的思想相似)   下面第一版代码中,依旧存在与上一篇第一版代码相同的问题——只能求解p数组中给出的最大限度。N>=10,代码就不能够求解出正确答案。(代码中你们都懂...
  • 即然耗时的原因是重复计算, 那么我们可以造⼀个「备忘录」,每次算出某个⼦问题的答案后别急着返 回,先记到「备忘录」⾥再返回;每次遇到⼀个⼦问题先去「备忘录」⾥查 ⼀查,如果发现之前已经解决过这个问题了,...
  • 正式应用动态规划。...与贪心算法试图通过局部最优解来组合成最优解的思想相似) 以下第一版代码中,依然存在与上一篇第一版代码同样的问题——仅仅能求解p数组中给出的最大限度。N>=10,代码就不可以求...
  • 动态规划(自底向上)

    千次阅读 2013-07-19 15:20:56
    动态规划 - 求解二项式系数(顶向下,自底向上) ref from http://jarg.iteye.com/blog/859391 博客分类: 算法设计 PascalJ# 1. 动态规划 备忘录备忘录方法采用顶向下方式,为每个解过的子问题建立了...
  • 二叉树之自底向上递归236. 二叉树的最近公共祖先652. 寻找重复的子树 二叉树我们知道使用递归代码会比较简洁,而这些递归题型中大部分题目都是上向(正常思维)进行递归,也有自底往上进行递归的题目,以下汇总...
  • 备忘录方法的递归方式是顶向下的,而动态规划算法则是自底向上递归的。 备忘录方法的控制结构与直接递归方法的控制结构相同 区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相...
  • 与动态规划算法不同的是,备忘录方法的递归方式是顶向下的,而动态规划算法则是自底向上递归的.因此,备忘录方法的控制结构与直接递归方法的控制结构相同,而区别在于备忘录方法为每个解过的子问题建立了备忘录以备...
  • 大家都知道,数值稍大的递归运行时间对于开发者来说就是场灾难,我们总是想方设法在优化递归,或者说不用递归,此文中从空间时间角度详细剖析以上三种算法的区别,以及运行原理,以斐波那契数为例, 编程语言java ...
  • 文章目录例题:顶向下的好处顶向下的函数结构详解:划重点:递归的结构:递归的原理:题目一(强烈建议用递归法):...相比自底向上来说,前期虽然痛苦,但是当你清楚结果体系,熟悉后,你会发现写dp递归法比递推法
  • 备忘录技术

    2012-01-31 17:15:23
    还是说矩阵连乘问题,在用动态规划来做的时候,是一种自底向上的路线,要接触m[1,n]就要先从一个矩阵的时候,2个连乘的时候,3个连乘的时候,开始一步步求,填好表,然后才可以求出n个矩阵连乘。 其实在想这道题目...
  • //缺点是复杂度与自底向上算法一样,但实际上更占资源,时间上慢 public static int lcs(char[] x,char[] y,int i,int j,int[][] bak) { if(bak[i][j] != -1) return bak[i][j]; if(i == 0 || j == 0...
  • 备忘录

    2014-04-15 12:22:00
    shell编程入门:...http://blog.csdn.net/v_JULY_v结构之法 麻省理工学院公开课:算法导论 http://v.163.com/special/opencourse/algorithms.html 谷歌:http://googless.jd-app.com/ 转载于:...
  • 枚举 备忘录法 最优规划对比

    千次阅读 2013-01-01 12:14:44
    可以参考案例 北大ACM1163 - The Triangle ...1.1.1 什么是顶向下和自底向上 顶向下是我要达到什么目标,然后分析需要什么次级目标,为了达到次级目标还需要更次级目标,依此类推。类似于领导分配任务,领导

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,987
精华内容 1,594
关键字:

备忘录算法自底向上