# 动态规划

> 动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。

- ID: m06021
- 分类: technical
- 领域: 算法

## 定义

将复杂问题分解为简单的子问题，并存储子问题的解（记忆化），避免重复计算。核心是状态转移方程。脚手架作用： 经验复用。解决大问题（如人生规划）时，不要每次都从头算。建立自己的“缓存库”，把解决过的小问题（如如何早起、如何写邮件）打包成模块。遇到大问题时，调用这些模块，只处理新增的复杂性。

## 机制

动态规划适用于具备"最优子结构"（全局最优含局部最优）与"重叠子问题"（子问题被重复计算）的问题。它通过记忆化（缓存子解）或自底向上制表，把指数级重复计算降为多项式，核心是写出正确的状态定义与状态转移方程。

## 练习

1）定义状态（能完整描述子问题的变量）；2）推导状态转移方程；3）确定边界/初始条件；4）用记忆化或制表求解，避免重复计算。

## 脚手架用法

经验复用。解决大问题（如人生规划）时，不要每次都从头算。建立自己的“缓存库”，把解决过的小问题（如如何早起、如何写邮件）打包成模块。遇到大问题时，调用这些模块，只处理新增的复杂性。

[阅读网页](https://thinkingmodels.site/entries/detail/m06021)