宜信普惠：揭秘动态规划的相关细节

动态规划，你了解吗，其基本原理及解题思路又是怎样的呢？

接下来，本文通过宜信普惠的简单分析，让我们了解动态规划的相关知识。

据宜信普惠了解，动态规划算法（Dynamic Programming，简称 DP）是一种很高深莫测的算法，你会在一些面试或算法书籍的高级技巧部分看到相关内容，状态转移方程，重叠子问题，最优子结构等高大上的词汇也可能让你望而却步。

动态规划区别于一些固定形式的算法（比如DFS、二分法、KMP），没有实际的步骤规定第一步第二步来做什么，所以准确的说，动态规划其实是一种解决问题的思想。这种思想的本质是：一个规模比较大的问题（可以用两三个参数表示的问题），可以通过若干规模较小的问题的结果来得到的（通常会寻求到一些特殊的计算逻辑，如求最值等）。

动态规划的基本思想：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。

动态规划算法的设计步骤：分析优化解的结构、递归地定义最优解的代价、自底向上地计算优化解的代价保存并获取构造最优解的信息、根据构造最优解的信息构造优化解。

宜信普惠提示，采用动态规划求解的问题的一般要具有以下个性质：最优化原理，如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理；无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响；有重叠子问题，即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

宜信普惠认为，动态规划将大问题分解为子问题，利用子问题的解逐步解决大问题。动态规划可以帮助在给定约束条件下找到最优解。每个动态规划算法都从一个网格开始，单元格中的值通常就是要优化的值，每个单元格都是一个子问题。