1. Toy模板网首页
  2. > Toy博客

动态规划入门

10月前 作者：周小末天天开心 分类：Toy博客 阅读(36) 违法举报

这篇具有很好参考价值的文章主要介绍了动态规划入门。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划入门

目录

基础入门理论

最大连续子串和

暴力求解

 DP

LCS最长公共子序列

 LIS最长上升子序列

数塔

最大子矩阵和

背包问题

01背包

完全背包

多重背包

基础入门理论

       动态规划是一种常见的算法设计方法，主要用于优化多阶段决策问题的求解过程，具有高效性和可靠性。其基本思想是将待求解问题分解成若干个子问题，逐个求解这些子问题，并保存每个子问题的结果，避免重复计算，以便快速地求出原问题的解。动态规划主要应用于最优化问题，如最长公共子序列、背包问题等。

动态规划算法主要有以下几个步骤：

  1. 定义状态：将原问题转化为子问题，定义状态表示子问题的解。

  2. 设计状态转移方程：根据状态之间的联系，设计状态转移方程，表示从子问题的解推导出原问题的解。

  3. 初始化：初始化子问题的解，即确定初始状态。

  4. 计算顺序：按照状态之间的依赖关系，按顺序计算子问题的解，直到计算出原问题的解。

  5. 输出解：输出原问题的解。

最大连续子串和

动态规划入门

 给出数组a，求出数组a中最大的连续子串的和。

暴力求解

两种方法，都是从起始点开始循环，但f2方法比f1优化了，没有去重复求出已经得到的结果。

import java.util.Arrays;

public class maxSubSum {
    public static void main(String[] args) {
        int[] a = {-2, 11, -4, 13, -5, 2};
        f1(a);
        f2(a);

    }

    public static void f1(int[] a) {
        int max = Integer.MIN_VALUE;//记录最大连续子串的和，先给定无穷小
        for (int start = 0; start < a.length; start++) {//穷举所有子串的起始点
            for (int len = 1; start + len <= a.length; len++) {
                //起始点固定，穷举长度分别为1-6的所有情况
                int sum = 0;
                for (int i = start; i < start + len; i++) {
                    sum += a[i];//sum为每次连续子串的和
                }
                max = Math.max(max, sum);//记录当前循环中最大的子串和
                System.out.printf("len=%d a[%d-%d] sum=%d\n",len, start, start + len, sum);
            }
            
        }
        System.out.println("最大子串和为：" + max);
    }

    public static void f2(int[] a) {
        int max = Integer.MIN_VALUE;//记录最大连续子串的和，先给定无穷小
        for (int start = 0; start < a.length; start++) {//穷举所有子串的起始点
            int sum = 0;
            for (int len = start; len < a.length; len++) {//从start开始一直循环到最后
                sum += a[len];//sum为每次连续子串的和
                max = Math.max(max, sum);//记录当前循环中最大的子串和
                System.out.printf("len=%d a[%d-%d] sum=%d\n",len, start, start + len, sum);
            }
        }
        System.out.println("最大子串和为：" + max);
    }
}

可以看出每次起始点和长度变化时sum的值。

动态规划入门

 DP

动态规划入门

判断dp[i  - 1]是否大于0，大于0时dp[i] = dp[i - 1] + a[i]，如果小于等于0那么dp[i] = a[i]。也就是在dp[i - 1] + a[i]和a[i]中取最大值赋给dp[i]。也可以理解为每一个问题都会用到前一个子问题的最优解

import java.util.Arrays;

//最大连续子串和
public class maxSubSum {
    public static void main(String[] args) {
        int[] a = {-2, 11, -4, 13, -5, 2};
        f3(a);
    }

    public static void f3(int[] a)  {
        int[] dp = new int[a.length];
        int max = Integer.MIN_VALUE;//记录最大连续子串的和，先给定无穷小
        dp[0] = Math.max(0, a[0]);
        for (int i = 1 ; i < a.length; i++) {
            dp[i] = Math.max(dp[i - 1] + a[i], a[i]);
            if (max < dp[i]) {
                max = dp[i];
            }
        }
        System.out.println(Arrays.toString(dp));
        System.out.println(max);
    }
}

得到运行后的dp数组以及最大子串的和

动态规划入门

LCS最长公共子序列

        最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。

给定两个字符串，找出这两个字符串中最大的公共子序列

s = BDCABA

t = ABCBDAB

动态规划入门

如果当前比较的两个字符相等，那么dp[i + 1][j + 1] = dp[i][j] + 1;如果不相等，那么dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);

例如如上表格中，dp[3][5]就表示字符串 BDC 和 ABCBD，公共子序列包含BD和BC，长度为2，所以dp[3][5] = 2。在其基础上都增加一个字符，也就是在dp[4][6]位置，表示字符串 BDCA 和 ABCBDA，增加的都是A字符，所以dp[4][6] = dp[3][5] + 1 = 3。

import java.util.Arrays;
import java.util.Scanner;

public class LCS {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s, t;
        while (scanner.hasNext()) {
            s = scanner.next();
            t = scanner.next();
            //dp[i][j]表示s1带si yu t1到tj的最长公共子序列
            int[][] dp = new int[s.length() + 1][t.length() +1];
            //因为s和t是从1开始的所以长度要+1
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < t.length(); j++) {
                    if (s.charAt(i) == t.charAt(j)) {
                        dp[i + 1][j + 1] = dp[i][j] + 1;
                    } else {
                        dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                    }
                }
            }
            System.out.println(dp[s.length()][t.length()]);
            for (int[] i:dp) {
                System.out.println(Arrays.toString(i));
            }
        }
    }
}

运行后求出最大公共子序列和表格

动态规划入门

 LIS最长上升子序列

        最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。对于固定的数组，虽然LIS序列不一定唯一，但LIS的长度是唯一的。例如给出如下序列 ( 2, 7, 1, 5, 6, 4, 3, 8, 9)，就饿可以得到最长上升子序列长度为5，但序列可以为 (2, 7, 6, 8, 9)，也可以为 (2, 5, 6, 8, 9)。

动态规划入门

import java.util.Arrays;
import java.util.Scanner;

public class LIS {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();//序列的长度
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            int[] dp = new int[n];
            Arrays.fill(dp, 1);//最小的上升子序列就是当前a[i]本身，例如 5 4 3 2 1
            int l = 0;//记录全局最长的上升子序列
            for (int i = 0; i < n; i++) {
                //dp[0],dp[1] ... dp[n - 1]
                for (int j = 0; j < i; j++) {
                    //求dp[i],需要穷举前[0, 1, .... i - 1]的子状态
                    if (a[i] > a[j]) {//硬性条件，因为只有这样才能和a[i]构成升序
                        dp[i] = Math.max(dp[i], dp[j] + 1);//因为已经默认了所有的最小子序列为1，所以这里dp[j]要+1
                    }
                }
                l = Math.max(dp[i], l);//将dp[i]或者当前的l最大的赋给l
            }
            System.out.println(Arrays.toString(dp));
            System.out.println(l);
        }
    }
}

 动态规划入门

数塔

动态规划入门

思路：可以从数塔的下方向上进行循环相加然后比较，如果从上向下无法选择哪一条路得到的结果是最大的。

找到状态转移方程为  a[i][j] += Math.max(a[i + 1][j], a[i + 1][j + 1]),  表示当前的这个数的值等于其下方或右下方两个值其中最大的一个，所以我们也可以判断出需要从倒数第二行进行增加，因为最后一行下方没有值。

import java.util.Arrays;
import java.util.Scanner;

public class numberTower {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//输入数据行数
        int[][] a = new int[n][n];//数组底和高长度都为n，三角形
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                a[i][j] = scanner.nextInt();//输入数据
            }
        }
        for (int[] b : a) System.out.println(Arrays.toString(b));

        //a[i][j] += Math.max(a[i + 1][j], a[i + 1][j + 1])
        for (int i = n - 2; i >= 0; i--) {//从倒数第二行开始dp，因为从倒数第一行开始的话无法获得最大值
            for (int j = 0; j <= i; j++) {
                a[i][j] += Math.max(a[i + 1][j], a[i + 1][j + 1]);
                //表示当前的这个数的值等于其下方或右下方两个值其中最大的一个
            }
        }
        System.out.println();
        for (int[] b : a) System.out.println(Arrays.toString(b));
        System.out.println(a[0][0]);
    }
}

得到经过节点之和最大为59

动态规划入门

最大子矩阵和

求矩阵中最大的子矩阵的和

动态规划入门

利用前缀和的思想，求出所有可能性子矩阵的前缀和，也就是将一个矩阵块利用前缀和快速的压缩成单行，然后找出这一行中最大的字段和

动态规划入门

 动态规划入门

import java.util.Arrays;
import java.util.Scanner;

public class maxSubmatrixArray {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//表示矩阵的长和宽的长度
        int[][] g = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                g[i][j] = scanner.nextInt();
                g[i][j] += g[i - 1][j];//按行同步计算二维数组的前缀和
            }
        }
        int ans = Integer.MIN_VALUE;//开始时先给最小值，用来存放子矩阵的最大的和
        for (int start = 1; start <= n; start++) {
            for (int end = 1; end <= n; end++) {
                //枚举从start到end行的矩阵块
                //从start到end行的矩阵块，我们可以用前缀和快速地压缩成单行的和
                int dpi = 0;
                for (int col = 1; col <= n; col++) {
                    int ai = g[end][col] - g[start - 1][col];//根据前缀和快速计算start行到end列的累加和
                    dpi = Math.max(dpi + ai, ai);
                    ans = Math.max(ans, dpi);
                }
            }
        }
        for (int[] x : g) System.out.println(Arrays.toString(x));
        System.out.println(ans);
    }
}

动态规划入门

背包问题

01背包

        01背包问题是一个经典的背包问题，是指一个固定容量的背包，以及一些物品，每个物品有自己的体积和价值，在不超过背包容量的情况下，将一些物品装入背包中，使得背包中物品的总价值最大。

给定5个物品，以及一个容量为10的背包，根据所有物品的价值，找出背包中物品总价值最大的值。

物品体积为：{2, 5, 4, 2, 3} 所对应的价值为：{6, 3, 5, 4, 6}

求解思路：

使用动态规划算法。先定义一个二维数组 dp，其中 dp[i][j] 表示前 i 个物品放入容量为 j 的背包可以获得的最大价值。对于第 i 个物品，它可以选择放入背包中或不放入背包中，所以对于每一个物品，我们需要遍历所有的背包容量 j，如果选择放入背包，那么它对 dp[i][j] 的贡献就是当前物品的价值，同时还需要考虑容量剩余 j - v[i] 的最大价值，即 dp[i - 1][j - v[i]]；如果选择不放入背包，那么它对 dp[i][j] 的贡献就是 0，容量也不需要修改。

所以，动态转移方程为：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])

import java.util.Arrays;
import java.util.Scanner;

public class beibao01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//n个物品的体积
        int m = scanner.nextInt();//背包的容量
        int[] v = new int[n + 1];//存放n个物品的体积,n+1是因为i从1开始
        int[] w = new int[n + 1];//存放n个物品的价值
        int[][] dp = new int[n + 1][m + 1];
        //dp[i][j]只考虑前i种物品，书包容量为j时为最后装载的价值
        for (int i = 1; i <= n; i++) {
            //输入每个物品的体积和价值
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {//穷举前i个物品的体积
            for (int j = 1; j <= m; j++) {//前i个物品的体积确定后穷举背包的容量
                if (j < v[i]) {
                    //如果当前物品的体积大于背包的容量，就相当于用第i - 1个物品去装j容量的背包
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //如果当前物品可以被背包装下，就要考虑价值的问题，可以选择装或者不装,取价值最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        for (int[] x : dp) System.out.println(Arrays.toString(x));
        System.out.println(dp[n][m]);
    }
}

得到规划后的数组以及最大的价值为17

动态规划入门

完全背包

        完全背包问题是一个经典的动态规划问题，它是背包问题的一个变种。在这个问题中，有一个固定大小的背包，和一些可放入背包中的物品。每种物品都有一个对应的价值和重量，无限个可用。需要确定如何选择物品放入背包，使得背包中物品的总价值最大。和0-1背包问题不同的是，在完全背包问题中，每个物品是无限可用的，可以选择多次放入。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        // 输入物品数量和背包容量
        int n = input.nextInt(); // 物品数量
        int m = input.nextInt(); // 背包容量

        // 初始化两个数组
        int[] w = new int[n + 1]; // 物品的重量
        int[] v = new int[n + 1]; // 物品的价值

        // 输入每个物品的重量和价值
        for (int i = 1; i <= n; i++) {
            w[i] = input.nextInt();
            v[i] = input.nextInt();
        }

        // 初始化dp数组，dp[i][j]表示前i个物品，容量为j的背包的最大价值
        int[][] dp = new int[n + 1][m + 1];

        // 递推求解dp数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 当前物品可以重复选择
                for (int k = 0; k <= j / w[i]; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
                }
            }
        }

        // 输出最大价值
        System.out.println(dp[n][m]);
    }
}

多重背包

        多重背包问题是背包问题的一种扩展，指的是有一批物品，每种物品有数量限制，每种物品的数量可以有多个，而背包的容量是固定的，目标是选取一些物品放入背包中，使得在物品数量不超过限制的前提下，背包中物品的总价值最大。

        和01背包问题相比，多重背包问题的每种物品可以选择多个，而01背包问题的每种物品只能选择一个。而和完全背包问题相比，多重背包问题的每种物品有数量限制，而完全背包问题的每种物品可以选择无限个。因此，多重背包问题是背包问题的中间难度，介于01背包和完全背包之间。

import java.util.Scanner;

public class MultipleKnapsack {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 物品数量
        int N = sc.nextInt();
        // 背包容量
        int V = sc.nextInt();

        // 物品价值数组
        int[] values = new int[N + 1];
        // 物品重量数组
        int[] weights = new int[N + 1];
        // 物品数量数组
        int[] nums = new int[N + 1];

        // 输入物品信息
        for (int i = 1; i <= N; i++) {
            values[i] = sc.nextInt();
            weights[i] = sc.nextInt();
            nums[i] = sc.nextInt();
        }

        // dp 数组，dp[i][j] 表示前 i 件物品，容量为 j 时的最大价值
        int[][] dp = new int[N + 1][V + 1];

        // 逐个物品考虑
        for (int i = 1; i <= N; i++) {
            // 逐个容量考虑
            for (int j = 0; j <= V; j++) {
                // 初始化 dp[i][j]，即前 i 件物品容量为 j 时的最大价值
                dp[i][j] = dp[i - 1][j];
                // 遍历物品数量，尝试更新 dp[i][j]
                for (int k = 1; k <= nums[i]; k++) {
                    // 如果当前容量 j 可以放下当前物品
                    if (j >= k * weights[i]) {
                        // 更新 dp[i][j]
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * weights[i]] + k * values[i]);
                    }
                }
            }
        }

        System.out.println(dp[N][V]);
    }
}

动态规划入门文章来源地址https://www.toymoban.com/news/detail-416319.html

到了这里，关于动态规划入门的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 算法刷题Day 38 动态规划理论基础+斐波那契数+爬楼梯

    动态规划的解题步骤： 确定 dp 数组（dp table）以及下标的含义 确定递推公式 dp 数组如何初始化 确定遍历顺序 举例推导 dp 数组 很基础

    2024年02月15日
    浏览(62)
  • 代码随想录第44天|动态规划：完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ

    代码随想录第44天|动态规划：完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ

    代码随想录 (programmercarl.com) 动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili 完全背包和01背包问题唯一不同的地方就是，每种物品有无限件 。 完全背包中的物品可以添加多次，所以要从小到大遍历： 518. 零钱兑换

    2024年04月25日
    浏览(43)
  • 算法训练第三十八天|动态规划理论基础、509. 斐波那契数 、70. 爬楼梯 、 746. 使用最小花费爬楼梯

    算法训练第三十八天|动态规划理论基础、509. 斐波那契数 、70. 爬楼梯 、 746. 使用最小花费爬楼梯

    参考：https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 动态规划是什么 动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。 所以 动态规划中每一个状态一定是由上一个状态推导出来的 ，这一

    2024年02月04日
    浏览(39)
  • 11.动态规划：树形DP问题、树上最大独立集、树上最小支配集、换根DP、树上倍增（LCA）【灵神基础精讲】

    11.动态规划：树形DP问题、树上最大独立集、树上最小支配集、换根DP、树上倍增（LCA）【灵神基础精讲】

    回溯和树形DP的区别（什么时候需要return结果？）：对于回溯，通常是在「递」的过程中增量地构建答案，并在失败时能够回退，例如八皇后。对于递归，是把原问题分解为若干个相似的子问题，通常会在「归」的过程中有一些计算。如果一个递归能考虑用记忆化来优化，就

    2024年02月04日
    浏览(41)
  • 动态规划の入门小题，适合0基础看

    动态规划の入门小题，适合0基础看

    动态规划 是一种作者认为比较牛逼的算法，原因是作者初学时非常困难，认为这玩意非常抽象，它往往在求一些最大，最小XXXX问题上有妙用，这篇文章可以帮大家简单理解一下DP的含义。 对了，这玩意也叫DP，原因是动态规划的英文原意是 （dynamic programming）。 然后我们以一

    2024年02月04日
    浏览(54)

  • 乘积最大子数组--动态规划

    乘积最大子数组 思路： 看到这个题的时候 要用DP的想法去做这道题 想到遍历到前面的值能不能为后面所用 假设有n个值 我们可以记录一下 第i个值的最大值是什么 怎么用到前面的值取判断 第i个值 可能正数 也可能是负数 如果是正数 那么我们乘以后面第i-1位的最大值 可以得

    2024年02月11日
    浏览(42)

  • 动态规划——最大子数组和

    最大子数组和 Time Limit:  1000 MS Memory Limit:  5000 KB Description Input Output Sample Input Sample Output 显然该题应使用动态规划的方法求解。 可以使用动态规划来求解最大子数组和。假设dp[i]表示以第i个元素结尾的最大子数组和，那么可以得到以下状态转移方程： dp[i] = max(dp[i-1]+a[i], a[

    2024年02月02日
    浏览(41)

  • 最大子数组和:动态规划

    Problem: 53. 最大子数组和 首先就是赋予dp[0]为nums[0],然后循环遍历数组判断dp[i-1]是否小于0，如果小于0那么dp[i]就是nums[i]，负责dp[i]就是dp[i-1]+nums[i],这样就可以保证每个dp[i]都是目前序列的最大值，最后返回最大的dp[i]就好 描述你的解题方法 时间复杂度: 添加时间复杂度, 示例：

    2024年02月05日
    浏览(43)
  • 动态规划 | 乘积最大

    动态规划 | 乘积最大

    原题链接 今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一

    2024年02月03日
    浏览(47)
  • 3.4动态规划--最大字段和

    3.4动态规划--最大字段和

    要好好学习这个难受难受超级难受的动态规划了，千万不要再沉迷在看剧和玩耍里面了。必须承认最近没有好好学习。 最大字段和书上介绍了三种解法：暴力、递归分治、动态规划 递归分治，一分为二，合并的时候有三种情况，注意考虑清楚 动态规划，最优解的数组b[j]表示

    2024年02月02日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包