动态规划

引言

动态规划与分治方法相似，都是通过组合子问题的解来求解原问题。

分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。

动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子问题）。

在这种情况下，分治算法会重复计算很多子问题，而动态规划会将子问题的解存储起来（如用数组），从而避免每次求解一个子问题都需要重新计算。

动态规划方法通常用来求解最优化问题，这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值的解。

我们称这样的解为问题的一个最优解（一个问题可能有很多最优解）。

动态规划的四个步骤

1. 求出一个最优子结构
2. 递归地定义最优解的值
3. 计算最优解的值，通常采用自底向上的方法
4. 利用计算出的信息构造一个最优解

DP萌新三步

1. 思考回溯应该怎么写
   1. 入参和返回值
   2. 递归到哪里
   3. 递归边界和入口
2. 改成记忆化搜索
3. 1比1翻译成递推

钢条切割

问题描述

给定一段长度为 n 英寸的钢条和一个价格表 $p_i(i=1,2,\dots,n)$ ,求切割钢条方案，使得销售收益$r_n$ 最大。注意，如果长度为 $n$ 英寸的钢条的价格 $p_n$ 足够大，最优解可能就是完全不需要切割。

解析

对每一英寸的钢条，我们总是可以选择切割或者不切割。那么可以考察从第 $i$ 个位置进行切割，然后再计算$r_i$ 和 $r_{n-i}$ 两段的最优解。因此这个问题的最优解由相关子问题的最优解组合而成。

然