EP41-Dynamic Programming

动态规划(Dynamic Programming)在上学的时候就没怎么懂，今天又学习了一番，但肯定不可能在一两个小时内学懂、讲清楚，所以这篇日报可能是比较粗浅的理解，后续可能会补充。

动态规划把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。

为了帮助理解，我们可以回忆一下高中时候学过的数学归纳法；
最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：

证明当n= 1时命题成立。

假设n=m时命题成立，那么可以推导出在n=m+1时命题也成立。（m代表任意自然数）

比如我们证明：

证明

我们会用一个递推得到n=k+1时成立，但是必须要用到第二步里的归纳的假设，不能利用消项把n = k 的这个假设给拆掉。

数学归纳法跟动态规划有什么联系？

动态规划最重要的一步就是构造「状态转移方程」（也有人说是怎么拆分问题最重要，我感觉差不多是一个意思）。

9 * n

怎么构造状态转移方程？比如计算9 * n，用dp(n) 表示 9 * n；
9 * 0 = 0 ;
9 * 1 = 0 + 9;
9 * 2 = 0 + 9 + 9;
用数学归纳法可以证明：9 * n=0 + 9 + ... + 9，n个9；有
dp(0)=9 * 0=0；
dp(1)=9 * 1=dp(0) + 9；
dp(2)=9 * 2=dp(1) + 9；
那么状态转移方程就是：
dp(n) = dp(n-1) + 9

最长递增子串(Longest Increasing Subsequence)

这是典型的动态规划问题，

求数列的最长上升（递增）子数列（LIS）的长度.
以1 7 2 8 3 4为例，
这个数列的最长递增子数列是 1 2 3 4，长度为4；
次长的长度为3，包括 1 7 8; 1 2 3 等.

我们一眼就能看出答案是1，2，3，4；那我们的脑子是怎么工作的？首先我们看到了1，加入队列；然后看到7，可以，下面就要找比7大的了，啊，8可以。这长度只有3，是IS但不是LIS啊。然后我们继续从头开始找，找到了LIS1234。注意，我们找找的了7之后找8，只要找第一个比7的大的数字了，不需要管7前面的数字。第i个阶段的最优解是由前i-1个阶段的最优解得到的，状态转移方程是：

LIS(i)=max{LIS(j)+1} ，j<i and a[j] < a[i]

注意后面的条件，j<i说明j最大可以取到i前面的一个数；a[j]<a[i]说明j后面一定有个数字可以增加LIS的大小。

动态规划与贪心法的一大区别是，动态规划有「无后效性」。「无后效性」指状态间的转移与如何到达某状态无关。

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；

另外，动态规划除了动态转移方程，还有一个特性，空间换时间，你需要记录之前子过程的最优解。比如之前的9 * n，如果你知道了9 * (n - 1)，再利用转移方程+9，瞬间就能得到结果了。

LIS的实现也用到了保存状态。而且保存的是每个位置的LIS，不能只保存前一个LIS，为什么，因为根据状态转移方程：LIS(i)=max{LIS(j)+1} ，j<i and a[j] < a[i]；
我们不但需要判断a[j]<a[i]，还要判断LIS[j]+1>LIS[i]啊，注意这个LIS[j]是从0~j的所有LIS，所以要保存之前每一个状态的LIS。

我就不贴代码了，看了一个三哥的视频，讲得不错，two pointers：
https://www.youtube.com/watch?v=CE2b_-XfVDk&t=311s&index=2&list=PLEd3CfWahaO09NWR8_0VLMqtrLxtm2DpJ

25 July 2017 Review

0/1背包

背包问题是讲解贪心和动归的好问题，而且有很多变种，比如物品可否分割（不能分割的就是0/1背包，要么选要么不选；可以分割的就不是0/1背包问题），同一重量的物品有多件等等。0/1背包指的是物品不能分隔并且同一重量的物品只有一件。

昨天晚上跟着之前讲解LIS的那个三哥的视频过了一遍0/1 Knapsack Problem，01背包问题，确实讲得非常清楚，DP就是这样，别人跟你讲了思路你就觉得清晰明了，自己想却很难构造最优子结构和状态转移方程。

三哥先是简单地提了一下非01背包，也就是物品可以split的情况。这种情况只要拿val/wt用non-increasing的顺序pick物品，如有需要，把最后一件能装的物品split一下就行了，这是贪心的思想。01背包就成了一道二维DP的问题。

构造一个二维Matrix dp[][]，每一行 i 代表每件物品选或不选，列 j 代表背包的容量从小到大。
dp[i][j]表示编号i以及i之前的物品都可以选择拿或者不拿，背包容量为j的情况下，最大能装的val。
状态转移方程：
dp[i][j] = Max(dp[i-1][j]) , val[i] + dp[i-1][j - wt[i] ])

我有个疑问是，这个wt是否要按照greedy的方式来排列，应该是不要的。

完全背包

同一件物品可以选择多件。

摘录

和01背包问题唯一不同的是j是从1到M。01背包问题是在前一个子问题（i-1种物品）的基础上来解决当前问题（i种物品），向i-1种物品时的背包添加第i种物品；而完全背包问题是在解决当前问题（i种物品），向i种物品时的背包添加第i种物品。

References:
[1]https://www.zhihu.com/question/23995189
[2]http://www.cnblogs.com/hapjin/p/5597658.html

EP41-Dynamic Programming