動态規劃算法 dynamic programming

    在大三上算法設計課程的時候，開始接觸了動态規劃，初學的時候沒什麼感覺，唯一的印象就是這種方法能逐漸根據最優子結構得到最終的最優解。也就是保證每一個子問題的解決得到的都是最優解，那最終得到的答案肯定也是最優解。動态規劃跟分而治之還是有點差別的，動态規劃的子問題之間關系緊密，而分而治之問題的解決，其子問題之間可以沒什麼太大的關聯性。這裡俺們就來看看動态規劃的方法以及運用。

    先看看曆史：

    上世紀40年代，richard bellman最早使用動态規劃這一概念表述通過周遊尋找最優決策解問題的求解過程。1953年，

richard bellman将動态規劃賦予現代意義，該領域被ieee納入系統分析和工程中。為紀念bellman的貢獻，動态規劃的核心

方程被命名為貝爾曼方程，該方程以遞歸形式重申了一個優化問題。

    要能使用動态規劃算法，首先是能将問題劃分成許多的小問題，然後必須能找出解決這些問題的最優結構，也就是最優子結構。

     一般，動态規劃的執行步驟是：

    (1)找出最優解的性質，并刻劃其結構特征。

      (2)遞歸地定義最優值。

      (3)以自底向上的方式計算出最優值。

      (4)根據計算最優值時得到的資訊，構造最優解。

     利用動态規劃算法可以用來解決一些經典的問題，比如矩陣連乘、最長公共子序列、背包問題、串編輯問題。還常常運用在生物資訊學、語言處理等領域中。

      1、矩陣連乘問題及最長公共子序列問題

           在部落格http://www.cnblogs.com/chinazhangjie/archive/2010/11/16/1878400.html中有詳細的解決步驟。

     2、背包問題

          主要是0/1背包問題：http://blog.csdn.net/dapengbusi/article/details/7463968

     3、串編輯問題

          http://qinxuye.me/article/get-edit-distance-by-dynamic-programming/

     4、最優二叉查找樹

         http://blog.csdn.net/qp120291570/article/details/8171661

     5、旅行商問題

         http://wiki.mbalib.com/wiki/%e6%97%85%e8%a1%8c%e5%95%86%e9%97%ae%e9%a2%98