动态规划.md

动态规划解题思路

先观察问题是否适合使用回溯（穷举）解决。

适合用回溯解决的问题通常满足“决策树模型”，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。

在此基础上，动态规划问题还有一些判断的“加分项”。

• 问题包含最大（小）或最多（少）等最优化描述。
• 问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。

相应地，也存在一些“减分项”。

• 问题的目标是找出所有可能的解决方案，而不是找出最优解。
• 问题描述中有明显的排列组合的特征，需要返回具体的多个方案。

问题求解步骤

动态规划的解题流程会因问题的性质和难度而有所不同，但通常遵循以下步骤：描述决策，定义状态，建立 dp 表，推导状态转移方程，确定边界条件等。

子问题分解是一种从顶至底的思想，因此按照“暴力搜索 → 记忆化搜索 → 动态规划”的顺序实现更加符合思维习惯

01 背包问题

背包问题是一个非常好的动态规划入门题目，是动态规划中最常见的问题形式

给定 n 个物品，第 i 个物品的重量为 wgt[i−1]、价值为 val[i−1] ，和一个容量为 cap 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。