动态规划

01背包问题

有n个重量和价值分别为$ w_i$ ,$ v_i$的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和最大的最大值。
例如，取n=4，W=5
$(w,v)={(2,3), (1.2), (3,4), (2,2)}$
递归解法：

/*rec(i,j)表示从第i个物品开始挑选总重量不大于j*/
int rec(i, j)
{
    int res;
    if (i == n){  /*没有剩余物品 , i <= n-1*/
        res = 0;
    }else if(w[i] > j){
        res = rec(i+1, j);
    }else{
        /*可以放下第i个物品*/
        /*       不挑选这个物品     挑选这个物品*/
        res = max(rec(i+1, j), rec(i+1, j- w[i] ) + v[i]);
    }
    return res;
}

 rec(0,W)

画出此程序的执行流程，可以发现程序计算了很多重复的问题,利用备忘录法，可以减小算法的复杂度
注意：数组是从0开始的，所以dp[0][m]表示的是选取第0个物品(数组中的索引为0，实际上是第一个物品)

int dp[n+1][W+1];  /*由于数组从0开始*/
int rec_memo(i, j)
{
    if (dp[i][j] >= 0){
        return dp[i][j];
    }
    int res;
    if (i == n){
        res = 0;
    }else if (w[i] > j){
        res = rec_memo(i+1, j)
    }else{
        res = max(rec_memo(i+1, j), rec_memo(i+1, j-w[i])+v[i]);
    }
    dp[i][j] = res;
    return res;
}

void main()
{
    memset(dp, -1, sizeof(dp));
    int ret = rec_memo(0,W);
    printf("%d\n", ret);
}

观察上面的二位数组，可以看出如下的递推公式

$$dp[n][j] = 0$$

$$dp[i][j] = \begin{cases} dp[i+1][j] & \text {j<w[i]} \\ max(dp[i+1][j], dp[i+1][j-w[i]]+v[i]) & \text{其他} \\ \end{cases}$$

此处需要注意的是：dp[0][m]
显然，上面的方程可以转换为以下的算法：

int dp[n+1][W+1];

int main()
{
    for(int i = n-1; i >= 0; i--)
        for(int j = 0; j< W; j++){
            if (j < w[i]){
                dp[i+1][j] = dp[i][j];
            }else{
                max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
            }
        }
    printf("%d\n", dp[0][W]);
}

观察发现，上面的二维数组i是逆序进行的，这是为什么了？我们先来看一下dp[i][j]所表示的意义：dp[i][j]表示前面i-1步骤已经进行完，剩余的重量为j，在给定的j下的最优选择。我们换一种思路，
dp[i+1][j]表示从前面i个物品中选出总重量不超过j时，总价值最大
那么就有如下递推公式：
$$dp[0][j] = 0$$

$$dp[i+1][j] = \begin{cases} dp[i][j] & \text{j<w[i]} \\ max(dp[i][j], dp[i][ j-w[i] ]+v[i]) & \text{其他} \\ \end{cases}$$

此时从(i+1, j)状态考虑，这个状态可能是由两种状态转移过来

(i, j)状态

(i, j-w[i])状态
这时就需要考虑j与w[i]的大小关系

int dp[n+1][W+1];

int main()
{
      for (int i= 0; i < n; i++)
        for(int j = 0; j <= W; j++ ){
            if(j<w[i]){
            //此时j<w[i]表明在总重为j的情况下，第i个物品已经不能被加入
                dp[i+1][j] = dp[i][j];
            }else{
            /*此时第i个物品可以加入到此重量j中，分为两种情况
             *第一种是没有加入第i个物品
             *第二种是将第i个物品加入到这里面
             */
                dp[i+1][j] = max(dp[i][j], dp[i][ j-w[i] ] + v[i]);
            }
        }
}

这里要这样理解此状态转移过程，前i个物品中选取总重量不超过j时的状态向前i+1个物品中选取总重不超过j和前i+1个物品中选取总重不超过j+w[i]时的状态的转移，此处是站在i状态考虑(i, j)，可以转换为以下两种状态

(i+1, j)状态
(i+1, j+w[i])状态

int dp[n+1][w+1];
int main()
{
    for (int i= 0; i < n; i++)
        for(int j = 0; j <= W; j++ ){
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            if(j + w[i] < W){
                dp[i+1][j + w[i]]=max(dp[i+1][j+w[i]],dp[i][j] + v[i]);
            }
        }
}

最长公共子序列

给定两个字符串$s_1,s_2,s_3…s_n$和$t_1,t_2,t_3….s_m$,求出最长公共子序列
可以定义二位数组dp[i][j]，该数组的定义为：

dp[i][j]:=$s_1, s_2, s_3….s_i$和$t_1, t_2, t_3….t_j$这两个序列的最长公共子序列的长度，故$s_1, s_2, s3….s{i+1}$和$t_1, t_2, t3…t{j+1}$的LCS的长度可能是，
如果$s{i+1} = t{j+1}$,那么长度就将加一
否则的话，可能就是$s_1, s_2, s_3,… s_i$与$t_1, t2, ….t{j+1}$的最长公共子序列，或者$s_1, s_2, s3,…s{i+1}$与$t_1, t_2,… t_j$的LCS,这两个LCS中最长的一个，用公式表示为：
$$dp[i+1][j+1] = \begin{cases} max(dp[i][j] + 1, dp[i+1][j], dp[i][j+1])& \text{ $s_{i+1} = t_{j+1}$ } \\ max(dp[i+1][j], dp[i][j+1]) & \text{其他} \\ \end{cases}$$

显然，以上的递推公式可以转换为：当0 < p < m,0 < q < n 时，p,q为其中的任意数
$$dp[0][p] = 0$$
$$ dp[q][0] = 0$$

$$dp[i+1][j+1] = \begin{cases} dp[i][j] + 1& \text { $s_{i+1} = t_{j+1}$ } \\ max(dp[i+1][j], dp[i][j+1]) & \mbox{其他} \\ \end{cases}$$

//给定的数组从下标1开始
int dp[n+1][m+1];

int main()
{
    for(int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (s[i] == t[j]){
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    printf("%d\n",dp[n][m]);
}