• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            什么是DP? 簡單地來說就是把一個問題分解成兩個或者多個小問題。然后先把小的問題解出來,最后利用已經得到的答案,把大的問題解決。
            它和分而治之有點類似,但有所不同。DP所分解出來的小問題會相互依賴,因此就不知道從哪里分。而分而治之的小問題不相互依賴。先看
            個小程序吧,生成第n個Fibnacci數,可能有人會這么寫
            int fib ( int n ) {
              if ( n == 0 )
                 return 1;
              if ( n == 1 )
                 return 1;
              return fib ( n - 1 ) + fib ( n - 2 );
            }
            但這個函數是2^n的遞歸,所以很快堆棧就會被用完的。另外如果思考一下,你會發現 fib( n - 1 ) 也已經要用到fib ( n - 2 ), 可是在
            算fib ( n ) 的時候,這個值又要算一遍,那為什么不把這個值存下來呢? 
            好, 我們就換個DP的方式:
            int fib ( int n ) {
               if ( n == 0 || n == 1 )
                  return 1;
               int [] f = new int[ n ];
               f[ 0 ] = 1;
               f[ 1 ] = 1;
               forint i = 2; i < n; i++)
               {
                    f[ i ] = f[ i-1 ] + f[ i-2 ];
               }
               return f[ n-1 ];
            }
            可能這個比較容易了。大家都明白,就是先把以前的值給算好,然后后面的計算就可以利用前面的值。嗯,那稍微換個難點的吧。給一個n*n的0,1 matrix,然后找到最大的全是1的submatrix的大小。比如:
            00011
            01111
            11110
            01110
            這個最大的那個全是1的submatrix的大小就是3.看起來挺難,其實蠻容易的。
            我們先用最平常的思路來解一下吧。
            先初始化另外一個同樣大小的n*n的matrix
            第一行和第一列很容易,和原先一樣的值
            00011
            0
            0
            1
            0
            接下來,算第二行,和其他的行。自己動手,你就知道其實就是
            s[i][j] = min(s[i][j-1],s[i-1][j],s[i-1][j-1]) + 1
            我們順便還可以加上一個max,記錄最大的值。
            這樣這個就搞定了。DP介紹完畢。接下來開始關于String的DP

            1.找到兩個字符串的最大相同字串的長度
            例如:abaabb aabbaa 最大的相同字串aabb長度就是4.
            解法:給兩個串 p,q 我們有
            c(i,j)  = 0 if p[i] != q[j]
            c(i,j)  = c(i-1,j-1) + 1 if p[i] = q[j].
            代碼和上面submatrix很相似。先初始化邊緣,然后算出其他的值
            2.找到兩個字符串的最大subsequence的長度
            例如:acbbab abbca 最大的subsequence is abba 長度是4.
            解法:給兩個串 p,q 我們有
            c(i,j) = max(c(i-1,j),c(i,j-1)) if p[i] != q[j]
            c(i,j) = c(i-1,j-1) + 1 if p[i] = q[j]
            3.找到一個字符串最大的Palindrom
            例如: abcdedcbdsa 最大的Palindrom就是bcdedcb 長度是7
            解法:給一個串p
            c(i,j) = max(c(i+1,j),c(i,j-1)) if p[i] != q[j]
            c(i,j) = c(i+1,j-1) + 2 if p[i] = q[j]


            posts - 16, comments - 16, trackbacks - 0, articles - 0

            Copyright © MichaelCao

            色诱久久av| 人妻久久久一区二区三区| 国产ww久久久久久久久久| 国产精品一区二区久久| 狠狠人妻久久久久久综合| 精品国产日韩久久亚洲| 亚洲国产精品无码久久98| 精品久久久久久99人妻| 97香蕉久久夜色精品国产 | 久久免费精品视频| 污污内射久久一区二区欧美日韩| 精品国产青草久久久久福利| 一本色道久久88加勒比—综合| 久久一本综合| 久久er热视频在这里精品| 亚洲日韩欧美一区久久久久我| A级毛片无码久久精品免费| 欧美一区二区精品久久| 婷婷久久久亚洲欧洲日产国码AV | 国产精品久久久天天影视香蕉| 久久e热在这里只有国产中文精品99| 囯产精品久久久久久久久蜜桃 | 欧美久久精品一级c片片| 99久久国产精品免费一区二区| 国产精品一区二区久久精品无码 | 国产精品热久久毛片| 久久久久人妻一区精品性色av| 久久99精品国产麻豆蜜芽| 久久人爽人人爽人人片AV| 久久久噜噜噜久久中文字幕色伊伊 | 国产成人综合久久精品尤物| 国产成人精品三上悠亚久久| 久久久无码精品亚洲日韩京东传媒 | 久久久久久久人妻无码中文字幕爆| 青青草国产97免久久费观看| 久久九九免费高清视频| 国产激情久久久久影院老熟女| 情人伊人久久综合亚洲| 亚洲综合久久综合激情久久| 国内精品久久久久影院免费| 1000部精品久久久久久久久|