Dynamic Programming

Posted on In

虽然之前也涉及到过动态规划，当然就是最经典的那个背包问题了，但是这么长时间过后，再看到类似的题，好像还是忘记了怎么做，所以在这里总结一下动态规划的内容，如果以后会遇到一些好的题目，也会陆陆续续的加入到这里来。

说到动态规划，这里有个图：

所以说，一直重复一件你已经知道答案的事情，是好事还是坏事呢？对于程序员来说，可能会认为是一件坏事，而这就是动态规划要说的地方：
永远记住你已经解决了的子问题的答案(To always remember answers to the sub-problems you’ve already solved.)
比如说有一台机器，现在要知道其t时刻的状态，而之前我们所做的一系列决定，都将决定t时刻的结果，但是我们事先或许都不知道，那么这些先前的结果将帮助我们选择未来的决定。
那么具体的，我们可以将问题分解陈一系列互相重叠的子问题，然后逐渐的从小开始解决更大的子问题。如果一个问题，可以被分为更小的子问题，而子问题又可以被分为更小的子问题，并且能设法找出一些重叠的子问题，那么这就是一个DP问题。
动态规划的核心就是通过记住部分结果来防止进行重复工作。
比如说以下这个例子：

Writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper.
“What’s that equal to?”
Counting “Eight!”
Writes down another “1+” on the left.
“What about that?”
“Nine!” “ How’d you know it was nine so fast?”
“You just added one more!”
“So you didn’t need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say remembering stuff to save time later!”

即证明了通过记住部分结果，能防止重复计算。

要解决的问题

动态规划算法的目的就是要解决多阶段决策问题，即：

初始状态->|决策1|->|决策2|->…->|决策n|->结束状态

适用范围

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

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

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

动态规划与递归(Recursion)的区别

动态规划从本质上来说就是递归+常识，也就是说递归能用其他函数的值来表达该函数的值，但是常识表示，如果预先完成递归的调用，并将其储存起来以方便访问，那么就能使得程序更快。而这就是记忆化(Memoization)，它记住了某些特定状态的结果，所以之后能通过访问来解决其它子问题。所以说动态规划背后的动机就是用空间交换时间。
比如对于斐波拉契函数来说：
纯递归：

1
2
3
4
5
int fib (int n) {
        if (n < 2)
            return 1;
        return fib(n-1) + fib(n-2);
    }

记忆化的动态规划

1
2
3
4
5
6
void fib () {
        fibresult[0] = 1;
        fibresult[1] = 1;
        for (int i = 2; i<n; i++)
           fibresult[i] = fibresult[i-1] + fibresult[i-2];
    }

大多数的动态规划问题可以分类为两类；

  1. 优化问题
  2. 组合问题

优化问题需要找出一个可行的解，以让给出的表达式的值最大或最小，而组合问题则要求给出做某件事有多少种方式，或者某事件发生的概率。

而动态规划有两种形式，Bottom up 或者 Top Down：
Bottom up: 想开始学习编程，所以开始练习，然后参加比赛，然后再训练，最后将成为优秀的程序员。
Top Down: 想成为优秀的码农，要怎么做呢？要辛苦工作，怎样呢？要努力锻炼，那又要怎么做呢？参加比赛，how？开始学习编程。

求解步骤

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

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

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

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

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

实际应用中可以按以下几个简化的步骤进行设计：

  1. 分析最优解的性质，并刻画其结构特征。

  2. 递归的定义最优解。

  3. 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值

  4. 根据计算最优值时得到的信息，构造问题的最优解