Nearth==>算法設計與分析/第三章/動态規劃算法(理論)

/*
一：定義
 動态規劃算法（我的了解）：
 相對于分治測政策來說，都是把一個大問題分解成若幹子問題。
 而唯一的不同在于，分治政策算法的所有子問題都有相同的性質以及相同的解決
 方法。動态規劃算法的子問題性質都不一樣，那麼針對每個不同性質的子問題，
 相應的解決方法也不同，所有針對大問題的最終結果來說，它的最優解為這些
 最優子問題的解得合并。
 ******************************************************************
 動态規劃算法（官方了解):
 動态規劃算法與分治法類似，其基本思想是将待求問題分解成若幹子問題，先求解子
 問題，再結合這些子問題的解得到原問題的解。與分治法不同的是,适合用動态
 規劃法求解的問題經分解得到的子問題往往不是互相獨立的。針對這些子問題，需要
 建立一個表來記錄所有已解決的子問題的答案，以後若遇到相同子問題，則查表記錄
 結果，避免重複計算，花銷太多時間。
 ----------------------------------------------------------------------
二：動态規劃算法适用于解最優化問題，它的大緻步驟如下
 1->找出最優解的性質，并刻畫其結構特征
 2->遞歸的定義最優值
 3->以自低向上的方式計算最優值
 4->根據計算最優值時得到的資訊,構造最優解
 ------------------------------------------------------------------------
三：動态規劃算法的基本要素
 針對一個問題,使用動态規劃算法來解決問題的基本要素展現在：最優子結構
 和重疊子問題。
 1->最優子結構：
 設計動态規劃算法的第一步通常是要刻畫最優解的結構。當問題的最優解包含了
 其子問題的最優解時，稱該問題具有最優子結構性質。問題的最優子結構性質提
 供了該問題可用動态規劃算法求解的重要線索。
 2->重疊子問題：
 可用動态規劃算法求解的問題應具備的另一基本要素是子問題的重疊性質。在
 用遞歸算法自頂向下解此問題時，每次産生的子問題并不總是新問題，有些子
 問題被反複計算。動态規劃算法正是利用了這種子問題的重疊性質，對每個子
 問題隻解一次，然後将其解儲存在一個表格中，當再次需要解此子問題時,隻是
 簡單地用常數時間檢視一下結果。通常,不同的子問題個數随問題的大小呈多項式
 增長。是以,用動态規劃算法通常隻需要多項式時間，進而獲得較高的解題效率。
 ---------------------------------------------------------------------
四：備忘錄方法
 備忘錄方法是動态規劃的變形。與動态規劃算法一樣，備忘錄方法用表格儲存
 已解決的子問題的答案，在下次需要解此子問題時，隻要簡單地檢視該子問題
 的解答，而不必重新計算。與動态規劃算法不同的是，備忘錄方法的遞歸方式
 是自頂向下的，而動态規劃算法則是自底向上遞歸的。
 */