Dynamic Programming 是一种把大问题拆成小问题来逐个击破的方法，it's all about subproblems.
概念上学会 Edit Distance, Longest Subsequence, 背包问题就基本可以理解它了。
先来说Longest Subsequence 问题吧。
假设我们有一串数字： [10, 9, 2, 5, 3, 7, 101, 18]
最长的上升序列是[2, 3, 7, 101]
这个问题可以被分成subproblem来做。什么叫subproblem？ 就是这个问题的迷你版。比如说这串数字只有[10]，很容易知道 Longest subsequence的长度为1.
如果是[10, 9] 那么longest len=1. 如果是[10, 9, 2] 因为是降序，所以Longest subsequence len还是1. 但是当子问题为[10 9 2 5]的时候发现，矮油，现在最长的生序列为 2 5 长度为2，有进步！ 当mini problem 变成[10, 9, 2, 5, 3, 7]时，2,3,7 也是生序列。
除了知道子问题以外，我们还需要找到每个问题之间的联系，子问题1 可以怎么样被子问题2拿来用？
经过研究发现， 前一个子问题保留下来的最长长度 + 1 如果比当前这个子问题还要长，那么最长长度应该是子问题长度+1. 【我这里描述的我自己都觉得不清楚。。。】
说说Edit Distance 问题。
求两个字符串中有几个不一样的字. 这里最关键的就是要画出DP的 table出来。 每一个Table的格子是一个subproblem的答案！
一般Dynamic Programming Table 的初始化都是将某些地方赋值初始值。 Edit Distance的话需要将first row/ first col全部初始化。 0,1,2,3,4,5...
自习想想就会知道为什么要这么做。 First Row初始其实就是等于比较 subproblem "E" 和 "P", "E"和"PO", "E"和"POL", "E"和POLY这些的差别数量。 很明显，差别由长的那一个来决定。 First Col同理。在有了最开始的row和col以后， 就可以从子问题逐渐推导出父问题的解了。 每一个格子可以说是代表了一个子问题， 这个问题的值是由它周围的三个格子决定的。因为只有那3个格子有办法通往当前的这个格子。
具体来说， 因为我们想要知道的是最小的differnece between two strings. 那么有3种情况，第一种情况：要么2个string最后一个letter一样，2个string最后一个字不一样。 那么result = diff+ E[i-1, j-1]. 第二种情况： 我们直接拿E[i, j-1]看看会不会给我们更短的result。第三种情况 E[i-1, j].
这里比较Tricky理解的就是： 好像只应该存在第一种情况阿，第二第三是什么意思？
比如说 abcd 和 abcde 其实第二个string比第一个string就多了一个letter，difference应该是1.
但是如果我们先比了最后一个letter，差别1 然后再加上differnece between [abc,和 abcd] 这样difference 至少会变成2. 我们不知道实际操作时候，3种情况哪个更短，所以都得实验一下，取最短的。
背包问题：
背包问题一直是我觉得DP里面最好玩的几个算法之一。
题目是，你现在在一家商店，商店里没人你可以随便偷东西。假设你有一个书包，书包可以装x kg，已知各个物品重量，价值。 我们最大容量只有15kg， 我们想要尽可能的往里面装价值高的东西并且最好不要有剩余空间浪费。 如下图， 如果我们装 15个 2块钱的东西，我们能偷30块走。 如果我们装1个12 kg的 再加3个1kg的凑满15公斤。我们偷走10块钱，这样不划算，少偷了！现在求一共最优的偷法。
首先，我们会发现这个是一个典型的DP问题。为什么？ 因为你回发现它是有很多子问题构成的，并且都遵守一样的条件。 比如说， 原问题是包可以装15kg。子问题可以是14kg对吧，13kg也可以阿。
然后我们要知道一个性质吧。比如说书包装capacity w的最优解里要装物品i，那么把物品i拿掉的话，子问题书包capacity w- wi 是子问题的最优解。
在所有物品里面，肯定起码有一个是我们要拿走的对吧，所以至少有一个会是我们最优解包里要放的物品。书包上限w的最优解= (书包装重w-wi的最优解 + 多拿走一个 物品i重量为wi的价值 )
也就是 k(w) = k(w- wi) + wi.
但是我们不知道哪一个物品是包含在最优解里的，所以得一个个试试比较。
K(w) = max(k(w- wi)+wi).
伪代码：
Initialize K array.
for w =1 to W:
K(w) = max(k(w - wi) + vi for all wi < w);
Run time = O(nW) 因为 每一步要测试n 个item。一共W步。
升级版背包问题：
基本版背包问题是说你可以拿走同样的东西 无限次，只要不超重。 假设现在你一个东西只能拿一次，那该怎么偷？
多加一个变量.
general 问题为： K(w, j)= 最优的偷法for 书包上限w 以及选取物品范围：1，2，3，4，。。。j.
求问题最优解： K(W, N).
K(w, j) = max{k(w- wj, j-1)+ vj, k(w, j-1)}.
怎么理解上面一行呢？ 为什么一会加vj 一会不加vj？
这是一个很经典的DP 思想。就是说如果这个东西加进来对我有帮助，加。 如果没帮助甚至倒退，那还不如不加。 为了判定到底是哪种情况，用一个max（a, b）来比较更好的哪一方。
伪代码：
Initialize k(0, j)= 0 and all k(w, 0) = 0;
for j = 1 to n:
for w = 1 to W:
if Wj > w: k(w, j) = k(w, j-1) //如果这个要偷的物品j直接妈的比我整个包能装重还大，无视。
else: k(w, j) = max{k(w, j-1), k(w-wj, j-1)+ vj} //因为你要偷j，你就得去掉包里之前装的某个物品来腾空间。未必价值能更高，所以要判断一下。
return k(w, n)
这么做的好处就是我们每个物品要么不偷，要么只偷一次。
子问题： k(w, j-1)为 1--j-1编号物品里一个最多只偷一次的最高价值偷法。
K(w, j)为子问题最优偷法 + 最后这个看偷不偷。
