Dynamic Programming

算法导论

What is Dynamic Programming?

Dynamic programming, like the divide-and- conquer method, but it applies when the subproblem overlap(subproblems share subsubprombles).

Where to apply?

We apply it to optimization problems. Such problems have many possible solutions. We want to find the smallset or the bigest.

Four steps

1.Characterizr the structure of an oprimal solution.
2.Recursively define the value of an optimal solution.
3.Compute the value of an optimal solution, typically in a bottom-up fashion.
4.Construct an optimal solurion from computed information.

15.1 Rod cutting

Find the best way to cut a rod, you can cut the rod in each sizes, and each length has a prise p_i(i is the length).And how can you find the bigest revenue?
You can compute all 2^n different ways.
But we also have a better way.
My code:

int s15(int n){//only to compute the length less than 10
    int array[100]={0};
    int p[11]={0,1,5,8,9,10,17,17,20,24,30};
    int res=0;
    if(n==1)
        return 1;
    for(int i=0;i<=n/2+1;i++){
        array[i]=p[i]+p[n-i];
    }
    res=max(array,10);
    return res;
}
int max(int a[],int len){//find the biggest number
    int t=-1;
    for(int i=0;i<len;i++){
        if(t<a[i])
            t=a[i];
    }
    return t;
}

We compute the biggest r_1 r_2 r_3 ...r_n,then we can compute r_n by p_i+p_n-i.Then we put them into recursive.
This way is inefficiebt. Because we compute the subprombles reapdly.So we use a array to memoized the result of subprombles.
It also can be simple.

11.27

5.2 Matrix chain

If we have a A_1 A_2 A_3 A_4...A_n, how can we do it the easiest?
For example:
(A_1 A_2)(A_3 A_4)
((A_1 A_2)A_3) A_4)
If there are 5*100 100*10 10*50 matrix to compute.We do the 5*100 100*10 will be more simple.
So we divie the A_i...j into A_i...k and A_k+1...j,then recursive them.

5.3动态规划的元素

什么时候应用

应用于的问题应该有两个重要组成部分，最优子结构和重叠子问题。存储会帮我们在自上而下的递归方法中更好的利用。

最优子结构

当一个问题有最优子结构，就是在暗示我们用DP，（也是贪心算法）
然后说到引入图，把顶点当成子问题，边当成选择一个子问题。

不是什么情况都可以动态规划

比如四个顶点，（连成一个正方形），求一个顶点到另一个顶点的最小距离可以动态规划，但是最大距离不可以动态规划。

11.29

15.4

一个问题

有两条DNA序列，他们的相似度是多少？
比如S1={A T C G G A T} S2={T C G A T A T T T}
他们共有的子序列是S3={T C G A T}(没有说一定是连续的)

解决办法

Step 1：定义一个最长的普通子序列

第一种办法是找到所有相同的子序列，但这是非常费时的。一个有m个元素的序列有2^m个子序列。
这个问题有最优子结构。比如X={x_1,x_2,x_3......x_n},他的一个子序列X_4={x_1,x_4,x_6,x_7}而X_0是一个空的序列。

Theorem 15.1(Optimal substructure of an LCS)

Let X=and Y=be sequences, and let Z=be any LCS of X and Y.
1.如果 x_m=y_n,然后Z_k=x_m=y_n,Z_k-1就是X_M-1和Y_N-1的LCS。
2.如果不等于，而且Z_k不等于x_m，z就是X_m-1 Y的LCS.
3.如果不等于，而且Z_k不等于y_n,Z就是X和Y_n-1的LCS.
proof

Step 2：递归解法

根据以上理论，当我们试图找出LCS时我们要检验一个或两个子问题。如果x_m=y_n我们就要找到X_m-1,Y_n-1的LCS。
当我们寻找解的时候，不外乎碰见以上三种情况，这样就可以递归求解。

Step 3：计算LCS的长度

LCS-LENGTH(X,Y)
m=X.length//x的长度
n=Y.length//y的长度
let b[1..m,1..n]andc[0..m,0..n]be new tables//新的表
for i=1 to m//这两个for循环为c初始化
    c[i,0]=0
for j=0 to n
    c[0,j]=0
for i=1 to m
    for j=1 to n
        if x_i==y_i//如果两个序列的元素匹配相等了（x第一个对y的第一个，第二个对第二个），j是增加的
            c[i,j]=c[i-1,j-1]+1
            b[i,j]="\"
        elseif//如果对应的元素没匹配到，执行这里
            c[i-1,j]>=c[i,j-1]
            c[i,j]=c[i-1,j]
            b[i,j]="^"
        else
            c[i,j]=c[i,j-1]
            b[i,j]="<"
return c and b

如果把这个伪代码写成程序执行，将b和c打在一个表格里，根据箭头指的方向就能找到相同的子序列，每一个斜箭头代表的地方就是子序列的一个元素。
后面提到了怎么print出这样一个表