动态规划

如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题。动态规划通过记录重叠子问题，来使下次碰到相同的子问题时直接使用之前记录的结果，以此避免大量重复计算。

动态规划的递归写法：

求斐波那契数列第n项的值，F(0) = 1,F(1) = 1。

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 100;
int dp[maxn];

int F(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    if (dp[n] != -1) {
        return dp[n];
    } else {
        dp[n] = F(n - 1) + F(n - 2);
        return dp[n];
    }
}

int main() {
    fill(dp, dp + maxn, -1);
    printf("%d", F(3));
    return 0;
}

动态规划的递推写法：

将一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字...第n层有n个数字。现在要从第一层走到第n层，每次只能走向下一层连接的两个数字中的一个，问最后将路径上所有数字相加后得到的和最大是多少？

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 1000;
int f[maxn][maxn], dp[maxn][maxn];//dp[i][j]代表从第i行第j个数字出发的到达底层所有路径中能得到的最大和

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf("%d", &f[i][j]);
        }
    }
    //边界
    for (int i = 1; i <= n; i++) {
        dp[n][i] = f[n][i];
    }
    //从第n-1层不断往上计算出dp[i][j]
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
        }
    }
    printf("%d\n", dp[1][1]);
    return 0;
}

使用递推写法的方式是自底向上，即从边界开始，不断向上解决问题，直到解决了目标问题；
而使用递归写法的计算方式是自顶向下，即从目标问题开始，将它分解成子问题的组合，直到分解至边界为止。

如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称这个问题拥有最优子结构。
一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划去解决。

区分 总结

1.最大连续子序列和

1007 Maximum Subsequence Sum

2.最长不下降子序列(Longest Increasing Sequence)

1045 Favorite Color Stripe

3.最长公共子序列(Longest Common Subsequence)

1045 Favorite Color Stripe

4.最长回文子串

1040 Longest Symmetric String

注：求最长回文子串最优的算法是Manacher（马拉车）算法。

5.DAG最长路

6. 01背包

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 100;
const int maxv = 1000;
int w[maxn], c[maxv];
int dp[maxn][maxv];//dp[i][v]表示前i件物品恰好装入容量为v的背包所能获得的最大价值
int main() {
    int n, v;
    scanf("%d%d", &n, &v);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    //边界
    for (int i = 0; i <= v; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= v; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    int max = 0;
    for (int i = 0; i <= v; i++) {
        if (dp[n][i] > max) {
            max = dp[n][i];
        }
    }
    printf("%d\n", max);
    return 0;
}

1068 Find More Coins

7.完全背包

和01背包唯一的区别就是状态转移方程由
max(dp[i - 1][j], dp[i-1][j - w[i]] + c[i])
变成了
max(dp[i - 1][j], dp[i][j - w[i]] + c[i]);

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 100;
const int maxv = 1000;
int w[maxn], c[maxv];
int dp[maxn][maxv];//dp[i][v]表示前i件物品恰好装入容量为v的背包所能获得的最大价值
int main() {
    int n, v;
    scanf("%d%d", &n, &v);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    //边界
    for (int i = 0; i <= v; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= v; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + c[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    int max = 0;
    for (int i = 0; i <= v; i++) {
        if (dp[n][i] > max) {
            max = dp[n][i];
        }
    }
    printf("%d\n", max);
    return 0;
}