---

前言

《华为机试真题》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。

如果您在准备华为的面试，期间有想了解的可以私信我，我会尽可能帮您解答，也可以给您一些建议！

本文解法非最优解（即非性能最优）。

动态规划的套路

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。

动态规划的题目比较多，比如：最长递增子序列问题、最短路径问题、背包问题、资源分配问题等。

动态规划并不是万能的，适用动态规划的问题必须满足最优子结构和无后效性。

• 最优子结构：动态规划问题一定会具备最优子结构，通过子问题的最值得到原问题的最值。
• 无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态࿰