1.定义及性质   


    动态规划是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，用时往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

2.算法设计步骤   

动态规划算法的设计可以分为4个步骤：

    动态规划法所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线图。动态规划法一般需要经历以下几个步骤：

    1.划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或是可排序的，否则问题就无法求解。

    2.确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

    3.确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来本阶段的状态。所以如果确定了决策，状态转移方程也就可以写出。但事实上尝尝是反过来做，根据相邻连个状态之间的关系来确定决策方法和状态转移方程。

    4.寻找边界条件：给出的状态转移方程是一个递推式，需要一个地推的终止条件或边界条件。

    实际应用中一般按一下步骤进行设计：

    1.描述最优解的结构，可以利用子问题的最优解来构造原问题的最优解；

    2.递归定义最优解的值

    3.按自底向上的方式计算最优解的值

    4.由计算出的结果构造一个最优解

   3.动态规划法的适用情况：   


  能采用动态规划求解的问题的一般要具有3个性质：

    (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

    (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

   （3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

4.算法实现说明   

    动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。

     使用动态规划求解问题，最重要的就是确定动态规划三要素：

    （1）问题的阶段 （2）每个阶段的状态

    （3）从前一个阶段转化到后一个阶段之间的递推关系。

     递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。

    确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

          f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}



    动态规划法的应用非常多，各大公司的笔试面试题也经常出现，如数组中的最长递增子序列问题、数组分割问题、数组的子数组之和的最大值问题。在后面的文章中会罗列动态规划法相关的面试题来逐个突破。加油！
---------------------
【转载，仅作分享，侵删】
作者：longshengguoji
原文：https://blog.csdn.net/longshengguoji/article/details/8806533
版权声明：本文为博主原创文章，转载请附上博文链接！

奈斯，感谢分享！