动态规划的一般解题步骤

数据结构与算法

1.步骤

1. 将原问题分解为子问题
2. 确定状态
3. 确定一些初始状态
4. 确定状态转移方程

2.动规问题的特点

1. 问题具有最优子结构性质
2. 无后效性

3.动规的三种形式

1. 记忆递归型
2. “我为人人”递推型
3. “人人为我”递推型