动态算法的四要素:动态规划算法是有适用场景的,在合适的场景下采用动态算法,才能体现这种算法的价值.

1.最优子结构:

如何判断一个问题是否具有最优子结构呢?对于一个问题而言,只有规模比该问题小,其他均与该问题一致的问题才可称为子问题.另外,子问题的决策不会对规模等大的问题产生影响,称为无后效性.当一个问题的最优解必然包含其子问题的最优解时,称该问题具有最优子结构.正因如此,将原始问题分解成一个个规模更小的子问题会更容易解决,最后将子问题的解结合成原始问题的解.

举例说明,假如每次只能一个台阶或两个,求爬n个台阶共有多少种方式.如果我们知道爬n-1层,n-2层台阶分别有多少种方式,就可以知道爬n层台阶有多少中方式.那么求爬n-1层楼就是求爬n层楼的子问题解题方法与思路是一致的

2.重叠子问题:

一般来说,具有最优子结构的问题总会让人想到把各个子问题看作相互独立的,因此会想到递归算法.但是在递归中会产生很多重复计算,而采用动态算法可以避免很多不必要的计算量.如上述爬楼梯的例子来说,解决规模为n-2,n-3的问题出现了很多次,意味着当采用递归方式时有许多重复计算,通过动态算法可以避免此问题,因为在解决n之前已经解决了n-1,n-2规模的子问题,直接取其结果即可,无需再次计算.

3.状态与状态转移方程:

这是动态算法的核心部分.在程序设计过程中,状态就是子问题的解,找到状态转移方程就是找到了子问题之间的递推关系,由此就可以自底向上地从子问题推出原始问题的解.动态规划算法可以实现只解决每个子问题一次就得出原始问题的答案.

4.边界条件:

边界条件就是程序 的停止条件,一般事原始问题的规模参数.当满足这种边界条件时,就可以得到原始问题的解.

综上所述,当一个原始问题具有这四个要素,就说明采用动态规划算法会比较高效的解决问题