> For the complete documentation index, see [llms.txt](https://jen-hsuan-hsieh.gitbook.io/letcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jen-hsuan-hsieh.gitbook.io/letcode/2.algorithm/27dong-tai-gui-hua.md).

# 2.7.動態規劃

## 1.Introduction

* 動態規劃是[分治法](https://jenhsuan.gitbooks.io/letcode/content/2.algorithm/23divide-and-conquer.html)的延伸
* 當遞迴分割出來的問題, 一而再、再而三出現, 就運用記憶法儲存這些問題的答案, 避免重複求解, 以空間換取時間
* 動態規劃的過程, 就是反覆地讀取數據、計算數據、儲存數據

## 2.使用動態規劃的時機

* 計算各種組合的數量
* 取得到現階段的某種可能數字 (例如: 最大值)

## 3.例子

* 1.[爬樓梯](http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html)
* 2\. 
* 3.地圖
  * 只能向下走或向右走, 有幾種可以到達目的地的走法?
  * 由於可以先知道前一步有多少種組合, 前一步又可以從前前一步的組合推得...

    * P\[i]\[j] = P\[i - 1]\[j] + P\[i]\[j - 1]

    ![](https://github.com/jenhsuan/letcode/tree/4999a189073590294b35b42c8dfe17f9b5bebfad/assets/螢幕快照%202017-05-22%20上午11.26.04.png)