[TOC]
# 参考资料
[知乎：什么是动态规划？](http://www.zhihu.com/question/23995189)
[百度百科：动态规划](http://baike.baidu.com/link?url=vGpz96tU-DsVSn91-qJK1NC9MrlwSi3TW9A_Cx6O6ReHSMX4mjP8EmsoR2Rgb1pF9yNDPbFilyKjIax2doSqUq)
[维基百科：动态规划](https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92)
每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。
# Introduction
Dynamic Programming is to solve combinatorial optimization problems,where we are looking for the best possible input to some function chosen from an exponentially large search space.
There are two part about DP.
*The first part is* programming technique:DP is essentially divide and conquer run in reverse:we solve a big instance of a problem by breaking it up recursively into smaller instances;but instead of carrying out the computation recursicely from the top down,we **start from the bottom with the smallest instances of the problem,solving each increasingly large instance in turn and storing the result in a table.**
*The second part is* design principle:in building up our table,we are careful always preserve alternative solutions we may need later,by delaying commitment to particular choices to the extent that we can.
* * * * *
因为动态规划解决的问题主要是组合最优解问题。对于分治，上一种状态和下一种状态没有过多的联系，我们主要考虑上一种唯一状态的返回结果就好，（n! = n*(n-1)!）。
但对于动态规划来说，它需要将前几种状态综合进行考虑，然后得出下一种状态的最优解。
那么，动态规划需要考虑俩点，一是最优子结构，一是重叠子问题。
* overlappings subproblems - memoization
* Table look-up
* Optional substructure:global optional sultion can be constructed from optional solvtions to sub-problems
### Memoization
```
int
memoFib(int n) {
int ret;
if(hashContains(FibHash,n)) {
return hashGet(FibHash,n);
}
else {
ret = memoFib(n-1) + memoFib(n-2);
hashPut(FibHash,n,ret);
return ret;
}
}
```
# 动态规划和分治
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
# Bottom-up and Top-down
Bottom-up：由简单到复杂，一般用迭代
Top-down：由复杂到简单，一般用递归
# 斐波那契数列
### 斐波那契数列的定义
> F(n) = F(n-1)+F(n-2),n>1;F(0) = 1;F(1) = 1;
### 最差递归实现
```
int f(int n) {
if(n <= 1) return 1;
return f(n-1) + f(n-2);
}
```
#### 为什么不好？
1. 递归调用过程中会出现很多重复计算的步骤。(因为递归树的原因)。如在计算f(4)的时候要计算f(3)和f(2)，而这里的值不会被保存下来，所以，f(3)中对f(2)仍然要计算一次。它的算法时间复杂度为O(a^n),a=1.628...
2. 递归调用会出现栈溢出的危险，它的空间复杂度也会随着n值的扩大而指数级增长。
### 改进版本1
```
int f(int n) {
int f0 = f1 = ret = 1;
int i;
for(i=1,i<n-1;i++) {
ret = f0+f1;
f0 = f1;
ret = f1;
}
return ret;
}
```
计算过程如下：
| n | 0 |1|2|3|...|
| -- | -- |--|--|--|
| f0 | 1|1|1|2|...|
| f1 | 1|1|2|3|...|
| ret | 1|2|3|5|...|
### 改进版本2
```
int f(int n) {
int *a = (int *)malloc(sizeof(int)*(n+1));
int i,ret;
a[0] = a[1] = 1;
for(i=2;i<n+1;i++)
a[i] = a[i-1]+a[i-2];
ret = a[i];
free(a);
reutrn ret;
}
```
### 改进版本3
利用Memoization来实现
```
//不太好，因为此处需要申明一个全局变量的数组。
#define SIZE (100)
int FibHash[SIZE] = {0};
int
hashContains(FibHash,n) {
if(n>=2 && FibHash[n] == 0) return 0;
return 1;
}
int
hashGet(FibHash,n) {
return FibHash[n];
}
void
hashPut(FibHash,n,ret) {
FibHash[n] = ret;
}
int
memoFib(int n) {
int ret;
if(hashContains(FibHash,n)) {
return hashGet(FibHash,n);
}
else {
ret = memoFib(n-1) + memoFib(n-2);
hashPut(FibHash,n,ret);
return ret;
}
}
```
# 1，3，5元面值若干，凑钱问题
### 算法思想
假如要计算11元需要的面值数最小，那么，11元减去一张1元或者3元或者5元，即10元，8元，6元分别需要的面值数，取出最小，加上1，即可以得到11元最小的。
所以，n元最小问题，是由n-1元，n-3元，n-5元三种状态里面取到的最优解。
其中计算的递归树为：
d(11) = min{d(10),d(8),d(6)} + 1
### 递推式
> d(i) = min{d(i-v)} + 1,其中v为面值1，3，5；i为求值
### 实现代码版本-1
```
#include <stdio.h>
#
#define AA (1)
#define BB (3)
#define CC (5)
#
//min
int min(int m,int n,int p) {
int ret = p;
if(ret > m) ret = m;
if(ret > n) ret = n;
return ret;
}
//主函数
int myAnswer(int y) {
int *a = (int *)malloc(sizeof(int)*(y+1));
int i,ret;
a[0] = 0;
for(i=1;i<y+1;i++) {
a[i] = min(a[i-AA],((i-BB)>=0) ? a[i-BB] : 0,((i-CC)>=0) ? a[i-CC] : 0)+1;
}
ret = a[y];
free(a);
return ret;
}
int main(int argc,char **argv) {
int answer = myAnswer(11);
printf("answer is %d",answer);
return 0;
}
```
# 最长非递减子序列（longest increasing subsequence）
### 算法思想
Suppose that we want to compute the Longest increasing Subsequence of an array.This is a sequence,not necessarily contiguous,of elements from the array such that each is strictly larger than the one before it.Since there are 2^n different subsequences of an n-element array,the brute-force approach of trying all of them might take a while.
***
假设有一个序列：
3 2 4 5 6 7 9 2
*d(1) = 1;(3)
d(2) = 1;(2)
d(3) = max{d(1),d(2)} +1 = 2;(4)
d(4) = max{d(1),d(2),d(3)}+1 = 3;(5)
d(5) = max{d(1),d(2),d(3),d(4)}+1 = 4;(6)
d(6) = max{d(1),d(2),d(3),d(4),d(5)}+1 = 5;(7)
d(7) = max{d(1),d(2),d(3),d(4),d(5),d(6)}+1 = 6;(9)
d(8) = max{d(2)}+1 = 2;(2)*
### 递推式（状态转移方程）
> d(i) = max{d(j)} + 1; a[i] >= a[j]
### 实现代码版本-1
```
#include <stdio.h>
int Lis(int *A,int n) {
int d[n];
int i,j;
int sum = 0;
int ret = 1;
if(n == 1) return ret;
for(i=0;i<n;i++) {
d[i] = 0;
//printf("%d\n",A[i]);
for(j=0;j<i;j++) {
if(A[j]<A[i] && d[j] > sum) {
sum = d[j];
}
}
d[i]=sum+1;
sum = 0;
if(d[i] > ret) ret = d[i];
}
return ret;
}
int main(int argc,char *argv[]) {
int A[] = {3,2,4,5,6,9,7,3,3,10};
int b = Lis(A,10);
printf("%d",b);
}
```
### 实现代码版本-2
```
#include <stdio.h>
#include <assert.h>
unsigned long
longest_increasing_sub(const int a[],unsigned long n,int *output) {
struct lis_data {
unsigned long length;
unsigned long prev;
}*table;
unsigned long best;
unsigned long scan;
unsigned long i;
unsigned long j;
unsigned long best_length;
if(n == 0) return 0;
table = (struct lis_data *)malloc(sizeof(*table)*n);
for(i=0;i<n;i++) {
table[i].length = 1;
table[i].prev = n;
for(j=0;j<i;j++) {
if(a[j]<a[i] && table[j].length+1 > table[i].length) {
table[i].length = table[j].length+1;
table[i].prev = j; //上一个子LIS的下标
}
}
}
best = 0;
for(i=1;i<n;i++) {
if(table[i].length > table[best].length) {
best = i;
}
}
best_length = table[best].length;
if(output) {
scan = best;
for(i=0;i<best_length;i++) {
assert(scan >=0);
assert(scan < n);
output[best_length-i-1] = a[scan];
scan = table[scan].prev;
}
}
free(table);
return best_length;
}
int main() {
int a[] = {2,12,3,4,5,6,4,2,2,12,4,56,8,42,100};
int n = 15;
int i;
int output[15] = {0};
int best = longest_increasing_sub(a,n,output);
for(i=0;i<best;i++){
printf("%d ",output[i]);
}
printf("\nbest_length is %d",best);
}
```
# 最长公共子序列（Longest Common Subsequence）
### 算法思想
### 递推式
### 实现代码版本-1
```
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <limits.h>
void
LCS(const char *x,const char *y,char *lcs) {
int xLen;
int yLen;
int i;
int j;
xLen = strlen(x);
yLen = strlen(y);
struct choice {
int length;
struct choice *prev;
char newChar;
}best[xLen][yLen];
for(i = 0;i < xLen;i++) {
for(j = 0;j<yLen;j++) {
best[i][j].length = 0;
best[i][j].prev = 0;
best[i][j].newChar = 0;
if(x[i] == y[j]) {
best[i][j].newChar = x[i];
if(i>0 && j>0) {
best[i][j].length = best[i-1][j-1].length+1;
best[i][j].prev = &best[i-1][j-1];
} else {
best[i][j].length = 1;
}
}
if(i>0 && best[i-1][j].length > best[i][j].length) {
best[i][j].length = best[i-1][j].length;
best[i][j].prev = &best[i-1][j];
best[i][j].newChar = 0;
}
if(j>0 && best[i][j-1].length > best[i][j].length) {
best[i][j].length = best[i][j-1].length;
best[i][j].prev = &best[i][j-1];
best[i][j].newChar = 0;
}
}
}
int outPos;
struct choice *p;
outPos = best[xLen-1][yLen-1].length;
//printf("%d",outPos);
lcs[outPos--] = '\0';
for(p = &best[xLen-1][yLen-1] ; p ; p = p->prev) {
if(p->newChar) {
assert(outPos >= 0);
lcs[outPos--] = p->newChar;
}
}
}
int main(int argc,char **argv) {
if(argc != 3) {
fprintf(stderr,"%s",argv[0]);
return 1;
}
// printf("%s%s%s",argv[0],argv[1],argv[2]);
char output[strlen(argv[1])+1];
LCS(argv[1],argv[2],output);
puts(output);
return 0;
}
```
# 0-1背包问题
（编程导论13集）
### 算法思想
#### 基于决策树的直观解法
W = [5,3,2]
V = [9,7,8];MAX = 5
Descion tree:
### 递推式
> F[i,j] = max{F[i-1,j],F[i-1,j-wi]+pi},j-w>=0
### 实现代码版本-1
```
/**
* 背包问题：weight=[3,4,5]
* value=[4,5,6]
* max = 10
*
* d[i][j] = max(d[i-1][j],d[i-1][j-w]+v)
*
*
*
*/
#include <stdio.h>
int pack(int w[],int v[],int n,int max) {
max++;
int i,j;
int A[n][max];
int with=0;
int without = 0;
int maxValue = 0;
for(j=0;j<max;j++) {
for(i=0;i<n;i++) {
A[i][j] = 0;
if(i == 0 && j-w[i]>=0) A[i][j] = v[i];
if(i-1>=0) without = A[i-1][j];
if(i-1>=0 && j-w[i]>=0) with = A[i-1][j-w[i]]+v[i];
//A[i][j] = with>without ? with : without;
if(A[i][j]<with) A[i][j] = with;
if(A[i][j]<without) A[i][j] = without;
if(A[i][j]>=maxValue) maxValue = A[i][j];
}
}
/*
for(j=0;j<max;j++) {
for(i=0;i<n;i++) {
printf("%d ",A[i][j]);
}
printf("\n");
}
*/
return maxValue;
}
int main(int argc,char **argv) {
int w[] = {3,4,5,6};
int v[] = {4,5,6,7};
int max = 13;
int n = 4;
int maxValue = 0;
maxValue = pack(w,v,n,max);
printf("%d",maxValue);
}
```
# 最大子段和
### 算法思想
### 递推式
> b[i] = max {a[i] , b[i-1]+a[i]}，取最大的b[i]
### 实现代码版本-1
```
#include <stdio.h>
int
MSS(int a[],int n) {
int *b = (int *)malloc(sizeof(int) * n);
b[0] = a[0];
int i=0,sum=b[0];
for(i=1;i<n;i++) {
b[i] = b[i-1]>0 ? (b[i-1]+a[i]) : a[i];
if(b[i]>sum) sum = b[i];
}
return sum;
}
int
main() {
int a[] = {3,5,-2,9,10,1};
int c = MSS(a,6);
printf("%d",c);
}
```
# 最长对称子序列
### 代码版本-1
```
#include <stdio.h>
int main(void) {
char str[100];
gets(str);
int b[100];
int i,j1,j2;
int max = 1;
b[0] = 1;
if(str[0] == str[1]) b[1] = 2;
else b[1] = 1;
for(i=2;i<strlen(str);i++) {
b[i] = 1;
j1 = i-1;
j2 = i-b[i-1]-1;
if(str[j1] == str[i]) b[i] = 2;
if(str[j2] == str[i]) b[i] = b[i-1]+2;
if(max < b[i]) max = b[i];
}
printf("%d",max);
return 0;
}
```
### 代码版本-2
```
#include <stdio.h>
int main(void) {
char str[100];
gets(str);
int b[100];
int i,j1,j2,j3;
int max = 1;
b[0] = 1;
if(str[0] == str[1]) b[1] = 2;
else b[1] = 1;
for(i=2;i<strlen(str);i++) {
b[i] = 1;
j1 = i-1;
j2 = i-b[i-1]-1;
j3 = i-2;
if(str[j2] == str[i]) b[i] = b[i-1]+2;
else if(str[j3] == str[i]) b[i] = 3;
else if(str[j1] == str[i]) b[i] = 2;
if(max < b[i]) max = b[i];
}
printf("%d",max);
return 0;
}
```
# 矩阵连乘问题
# 凸多边形最优三角剖分
# 多边形游戏
# 图像压缩
# 电路布线
# 流水作业调度
# 最优二叉搜索树
