基础入门理论
动态规划是一种常见的算法设计方法，主要用于优化多阶段决策问题的求解过程，具有高效性和可靠性。其基本思想是将待求解问题分解成若干个子问题，逐个求解这些子问题，并保存每个子问题的结果，避免重复计算，以便快速地求出原问题的解。动态规划主要应用于最优化问题，如最长公共子序列、背包问题等。
动态规划算法主要有以下几个步骤：
定义状态：将原问题转化为子问题，定义状态表示子问题的解。
设计状态转移方程：根据状态之间的联系，设计状态转移方程，表示从子问题的解推导出原问题的解。
初始化：初始化子问题的解，即确定初始状态。
计算顺序：按照状态之间的依赖关系，按顺序计算子问题的解，直到计算出原问题的解。
输出解：输出原问题的解。
最大连续子串和
给出数组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]); } }
