动态规划框架讲解

1.首先要明确动态规划的概念；

    1.动态规划是一个思想，而不是一个特定的算法。

    2.动态规划作为一种思想通常用来解决最优解的问题；

————————————————————————————————————————————————————

2.解题框架

    可以用动态规划解决的题目，通常具有一定的相似性；

    这些相似性包括但不限于：

        1.通常该问题是一个求最优解的问题

        2.该问题一定具有最优子结构

        3.一般具有重叠子问题的性质

        4.可以抽象为一个状态，并不同的状态之间可以转移

    概念讲解

        最优子结构：如果一个问题的一个最优解中包含了子问题的最优解，这个性质叫最优子结构；

                            求解动态规划问题的重点就是要描述这个问题的最优子结构；

        重叠子问题：就是字面上的意思，进一步解释就是在求解的过程中，碰到的子问题可能已经出现过了

        状态：           一个问题可以抽象为一个状态，如何定义状态在动态规划中特别重要（因为定义状态

                               就相当于描述了这个问题的最优子结构）；

    接下来我会用一个典型的例子和通过讲解大量的例题来描述这个框架。

————————————————————————————————————————————————————

3.斐波那契

    我将通过讲解如何求斐波那契第n项这个例子来大致描述一下动态规划的解题框架

    斐波那契的递推式如下

    这个问题是这样的，求解出斐波那契第n项；

    当然这是个很简单的问题(当然是在n比较小的情况，这里不讨论n比较大的情况),这里主要想借助这个题来讲解如何

    描述动态规划的解题框架；

    动态规划的解题步骤

    1.定义状态(其实也就是描述最优子结构)

    2.描述不同状态如何转移(一般可以求出一个状态转移方程)

    3.按一个方向(一般都是自底而上)求出该问题的解

    以下是是用动态规划的思想来求解斐波那契第n项

    在讲解之前首先要说明一下，这并不是一个典型的动态规划的问题，这里只是借助这个问题来大致描述一下动态规划

    的解题框架

    1.首先定义状态dp[i]，dp[i]是指当n为i时，斐波那契的值；

    2.定义完状态后，我们来根据题意给出的信息来描述不同的状态如何转移

       可以看出dp[i]等价于f(i),可以推出dp[i]可以由dp[i-1]和dp[i-2]推出；

       所以dp[i] = dp[i-1] + dp[i-2];

        这里特别指出dp[1],dp[2]是最初的状态，之后所有的状态都会由这两个状态转移过来。

        所以我们首先要定义dp[1],dp[2]的值，这叫做初始化

    3.按一个方向来求出dp[i]的值

        这里是按自底而上的方向求出值；

        这个过程可以用一个树形结构来表示

      1.最优子结构

            从图中可以看到如果要求解斐波那契的第i项,必须要求出斐波那契的i-1项和斐波那契的第i-2项；

            换句话说就是斐波那契的第i项的解包括斐波那契的第i-1项和斐波那契的i-2项的解；这个性质就叫做最优子结构

            也就是一个问题的一个最优解中包含了子问题的最优解

      2.重叠子问题

           可以看出某些状态(或者说是子问题)被多次调用，这个性质就叫做重叠子问题。

      3.为什么要自底而上的求解

            自底而上的求解可以避免重复计算重叠的子问题

 当然动态规划的问题不会像这个问题那样简单，但是解题框架都是一样的，下面通过讲解大量的典型例子和例题来

 更深一层的理解这个框架

————————————————————————————————————————————————————

4.典型例子和例题讲解

————————————————————————————————————————————————————

1.基础背包问题详解

2.状压dp讲解

3.浅谈动态规划优化