美文网首页
动态规划

动态规划

作者: 1nvad3r | 来源:发表于2020-09-10 18:49 被阅读0次

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

    动态规划的递归写法:

    求斐波那契数列第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;
    }
    

    相关文章

      网友评论

          本文标题:动态规划

          本文链接:https://www.haomeiwen.com/subject/fsupektx.html