动态规划与记忆化搜索

佚名 6年前 (2019-04-10) 随笔 914人围观抢沙发百度已收录

1. 01背包

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　递推式：

　　注意这里的物品在数组中是从 0 开始的。

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

2. 最长公共子序列问题 (LCS, Longest Common Subsequence)

　　这里我们定义 dp[i][j] = s1 ...... si 和 t1.....ti 为对应的 LCS 的长度

　　那么， s1 ..... s _i+1 和 t1 ..... t _i+1对应的公共子列可能是下面三种情况：

　　（1）当 s _{i+1 = t _i+1 时， LCS 就是在末尾追加上s _{i+1 ；}}

　　（2） LCS 为 S1 ..... Si 和 t1 ..... t _i+1的公共子列

　　（3）LCS 为 s1 ..... s _{i+1 和 t1.....ti}的公共子列

由此就可以得到递推式：

int n, m;
char s[MAX_N], t[MAX_M];

int dp[MAX_N + 1][MAX_W + 1];

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

3.完全背包问题

　　这次相比于 01 背包，同一种的物品可以取任意多件了，那么我们再试着写递推式：

　　还是令 dp[i + 1][j] = 从前 i 种物品挑选总重量不超过 j 时总价值的最大值。那么递推关系为

int dp[MAX_N + 1][MAX_W + 1];

void solve() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= W; j++)
            for (int k = 0; k * w[i] <= j; k++) 
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k * w[i]] + k * v[i]);
    printf("%d\n", dp[n][W]);
}

　　这里有三重循环，时间复杂度有0 （nW²），这样并不理想。当我们仔细分析整个过程会发现有一些重复计算。下面我们打表看一下 dp 数组的结果分析一下：

　　这里我们来以 dp[3][5] 和 dp[3][7] 为例来分析一下：

　　可以看出 dp[i+1][j] 递推过程中 k ≥ 1 的部分计算已经在 dp[i + 1][ j - w[i] ] 中计算完成了。

　　这样就不需要关于 k 的循环了，优化后的时间复杂度为 0（nW）。

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

　　此外，前面的 01背包和这里的完全背包问题，可以通过不断重复利用一个数组实现，来降低空间复杂度。

　　01 背包问题情况

int dp[MAX_N + 1];

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

　　完全背包问题情况

int dp[MAX_N + 1];

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

　　像这样写的话，两者的差异就变成了只有循环的方向了。重复利用数组可以节省内存空间，但使用不好可能会留下 bug ，所以使用要小心。不过出于节约内存的考虑，有时候必须要重复利用数组，也存在通过重复利用数组能够进一步降低复杂度的问题。

4. 01背包问题2

　　这一问题与最初的01背包问题相比，修改了限制条件。此前的方法复杂度为0（nW），对这一问题的规模就不够用了。在这个问题中，价值的范围比质量要小，所以采用DP针对不同价值计算最小的重量。

　　定义 dp[i + 1][j] = 前 i 个物品中挑选出价值总和为 j 时总重量的最小值（不存在时就是一个充分大的数INF）。由于前 0 个物品中无法挑选，所以初始值为：

　　 dp[0][0] = 0;

　　dp[0][j] = INF;

　　此外，我们考虑前 i 个物品中挑选出价值总和为 j 时，一定有

　　　　　（1）前 i-1 个物品中挑选价值总和为 j 的部分；

　　　　　（2）前 i-1 个物品中挑选价值总和为 j - v[i] 的部分，然后再选中第 i 个物品。

　　得到递推式：

　　dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])

　　通过这样求解，复杂度就变成了 0（n ∑_iv_i），当然，如果价值范围变大这个算法也不适用了。

int dp[MAX_N + 1][MAX_N * MAX_V + 1];

void solve() {
    fill(dp[0], dp[0] + MAX_N * MAX_V + 1, INF);
    dp[0][0] = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= MAX_N * MAX_V; j++) {
            if (j < v[i]) 
                dp[i + 1][j] = dp[i][j];
            else
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    int res = 0;
    for (int i = 0; i <= MAX_N * MAX_V; i++)
        if (dp[n][i] <= W)
            res = i;
    printf("%d\n", res);
}

5.多重部分和问题

　　定义： dp[i + 1][j] = 用前 i 种数字是否能加成 j

　　为了前 i 种数字能够加成 j ，也就需要能用前 i - 1 个数字加成 j，j - ai，... j - m * ai 中的某一种。由此可得递推式：

　　dp[i + 1][j] = (0 ≤ k ≤ m, 且 k * ai ≤ j 时存在使 dp[i][j - k * ai] 为真的k ）

int n; // 数列长度
int K; // 目标和数
int a[MAX_N];  // 值
int m[MAX_N];  // 个数

bool dp[MAX_N + 1][MAX_K + 1];

void solve() {
    dp[0][0] = true;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= K; j++)
            for (int k = 0; k <= m[i] && k * a[i] <= j; k++)
                dp[i + 1][j] |= dp[i][j - k*a[i]];
    if (dp[n][K]) printf("YES\n");
    else printf("NO\n");
}

　　这个算法复杂度为 0（K ∑m），还可以继续优化。在这个问题中，我们不光求出能否得到目标的和数，同时把得到时 ai 这个数还剩下多少个可以使用计算出来，这样就可以减少复杂度。

　　定义： dp[i + 1][j] = 用前 i 种数加和得到 j 时第 i 种数最多能剩余多少个（不能加和得到 i 的情况下为 -1）

　　这样如果前 i-1 个数加和能得到 j 的话，第 i 个数就可以留下 mi 个。此外，前 i 种数加和出 j - ai 时第 i 种数还剩下 k （k > 0）的话，用这 i 种数加和 j 时第 i 种数就能剩下 k - 1个。可得如下递推式：

　　　这个可以在 0（nK）时间内计算出结果

int dp[MAX_K + 1];

void solve() {
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= K; j++) {
            if (dp[j] >= 0)
                dp[j] = m[i];
            else if (j < a[i] || dp[j - a[i]] <= 0)
                dp[j] = -1;
            else
                dp[j] = dp[j - a[i]] - 1; 
        }
    if (dp[n][K]) printf("YES\n");
    else printf("NO\n");
}

6.最长上升子序列问题（LIS， Longest Increasing Subsequence）

　　　定义： dp[i] = 以 ai 为末尾的最长上升子序列的长度

　　以 ai 结尾的上升子序列是：

　　　　（1）只包含 ai 的子序列

　　　　（2）在满足 j < i 并且 aj < ai 的以 aj 为结尾的上升子序列末尾，追加上 ai 后得到的子序列

　　递推关系： dp[i] = max { 1, dp[j] + 1 | j < i 且 aj < ai } 时间复杂度 0（n²）

int n; 
int a[MAX_N];

int dp[MAX_N];

void solve() {
    int res = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        res = max(res, dp[i]);
    }
    printf("%d\n", res);
}

　　还可以继续优化。前面我们利用 DP 求去针对最末尾的元素的最长的子序列。如果子序列的长度相同，那么最末尾的元素较小的在之后会更加有优势（因为更小的更容易在下一个得到更新），所以我们再反过来用 DP 针对相同长度情况下最小的末尾元素进行求解。

　　定义：dp[i] = 长度为 i+ 1 的上升子序列中末尾元素的最小值（不存在的话就是INF）

　　接下来我们看看如果用 DP 来更新数组。

　　最开始 dp[i] 的值全部初始化为 INF，然后从前到后扫描，对于每个 aj ，如果 i = 0 或者 dp[j - 1] < aj 的话，就用 dp[i] = min(dp[i), aj ) 进行更新，最终找出使得 dp[i] < INF 的最大的 i +1就是结果了。这个 DP 直接实现的话还是 0（n²），但是对于每个 aj 最多只需更新 1 次，由于 dp 数组是递增的，我们可以利用二分搜索，这样就可以在 0（n log n）内得出结果。

int dp[MAX_N];

void solve() {
    fill(dp, dp + n, INF);
    for (int i = 0; i < n; i++) 
        *lower_bound(dp, dp + n, a[i]) = a[i];
    printf("%d\n", lower_bound(dp, dp + n, INF) - dp);
}