# 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/%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202017-05-22%20%E4%B8%8A%E5%8D%8811.26.04.png)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jen-hsuan-hsieh.gitbook.io/letcode/2.algorithm/27dong-tai-gui-hua.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.