2.7.動態規劃

1.Introduction

• 動態規劃是分治法的延伸

• 當遞迴分割出來的問題, 一而再、再而三出現, 就運用記憶法儲存這些問題的答案, 避免重複求解, 以空間換取時間

• 動態規劃的過程, 就是反覆地讀取數據、計算數據、儲存數據

2.使用動態規劃的時機

• 計算各種組合的數量

• 取得到現階段的某種可能數字 (例如: 最大值)

3.例子

• 1.爬樓梯

• 2.

• 3.地圖

  • 只能向下走或向右走, 有幾種可以到達目的地的走法?

  • 由於可以先知道前一步有多少種組合, 前一步又可以從前前一步的組合推得...

    • P[i][j] = P[i - 1][j] + P[i][j - 1]