07贪心 + 动态规划（D1_基础学习）

目录

讲解一：贪心算法

一、什么是贪心算法？

二、贪心算法的应用场景

三、使用Java代码实现贪心算法

四、知识小结

--------------------------------

讲解二：动态规划算法

一、什么是动态规划算法

二、动态规划算法求解问题需要具备的基本要素

1. 重复子问题

2. 最优子结构

3. 动态规划算法与分治算法的异同点

4. 动态规划求解的基本步骤

三、列举 7 个常见动态规划算法

1. 数字三角形

1.1. 经典递归解法

1.2. 备忘录法

1.3. 动态规划法

思路一

思路二

2. 最长公共子序列

2.1. 穷举搜索

2.2. 备忘录法

2.3. 动态规划

2.4. 改进

3. 最大子段和

4. 最长公共子串

4.1. 暴力法

4.2. 动态规划

5. 矩阵连乘

6. 最长递增子序列

7. 0-1背包问题

---

讲解一：贪心算法

一、什么是贪心算法？

贪心算法是一种思路简单、实现较为容易、效率较高的算法。

它的核心思想是：每一步都选择当前局部最优解，并且期望通过不断的选择来达到全局最优解。

贪心算法主要分为两个部分：选择策略和优化问题。

选择策略指的是，每一步如何从多个选项中选择一个局部最优解，而优化问题指的是，当已经选

择了一个局部最优解后，如何把问题规模缩小，以便下一步仍然能够找到局部最优解。

二、贪心算法的应用场景

通过上面介绍，我们知道贪心算法（Greedy Algorithm）是一种经典的解题思路，它通过每一步

的局部最优解，来达到全局最优解的目的。

它通常在数据规模较小且问题有最优子结构的情况下，具有较高效率，并且与动态规划算法、分

治法等常用算法相比，贪心算法的实现较为容易。

它还经常被用来解决优化问题，例如：

1、集合覆盖问题：有一些广播台，每个广播台可以覆盖一些地区，求出覆盖所有地区需要选择

哪些广播台。

2、背包问题：有一个固定大小的背包，要尽可能装入最有价值的物品，求最大价值量。

3、旅行商问题：有一个旅行商需要访问多个城市，每个城市之间的距离已知，求最短的访问距

离。

4、区间调度问题：一个工厂有许多订单需要进行生产，每个订单都有一个开始时间和结束时

间，求如何排列生产顺序，才能完成尽可能多的订单。

三、使用Java代码实现贪心算法

下面我们以背包问题为例，来演示如何使用Java代码实现贪心算法。

假设有一个装有可重复使用的商品的背包，商品的价值不同，重量也不同，背包只能装载固定重

量的商品，怎样才能使背包中的商品价值最大？

我们可以采用择单价最高的商品策略，先放入单价最高的商品，直到背包无法再容纳下一个商

品，再取第二高价值的商品，依此类推。

以下是Java代码示例：

public class Knapsack {public static double fractionalPack(int capacity, int[] values, int[] weights) {int n = values.length;double maxValue = 0.0;  // 最终最大价值double[] fractions = new double[n];// 计算每个商品的单位价值for (int i = 0; i < n; i++) {fractions[i] = (double) values[i] / weights[i];}// 按单位价值从高到低排序，采用冒泡排序for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if (fractions[i] < fractions[j]) { // 如果i商品的单位价值小于j商品的单位价值，则交换double temp = fractions[i];fractions[i] = fractions[j];fractions[j] = temp;//对应的values和weights也需交换temp = values[i];values[i] = values[j];values[j] = (int) temp;temp = weights[i];weights[i] = weights[j];weights[j] = (int) temp;}}}//依次选择单位价值最高的物品for (int i = 0; i < n; i++) {if (weights[i] <= capacity) {capacity -= weights[i];maxValue += values[i];} else {maxValue += fractions[i] * capacity;break;}}return maxValue;}
}

四、知识小结

贪心算法是一种经典的解题思路，在实际应用中，很多问题可以用贪心算法求解。Java语言作为

一种广泛应用的编程语言，也支持贪心算法的实现。为了能够更好的掌握贪心算法，我们需要不

断学习和实践，并理解贪心算法的基本思想和应用场景，不断提高自己的算法和编程能力。

--------------------------------

讲解二：动态规划算法

一、什么是动态规划算法

（1）动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题

（2）经分解得到的子问题往往不是互相独立的，有些子问题被重复计算多次

（3）如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量

重复计算，从而得到多项式时间算法（备忘录法）

（4）图解：

二、动态规划算法求解问题需要具备的基本要素

1. 重复子问题

• 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质
• 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果
• 通常不同的子问题个数随问题的大小呈多项式增长，用动态规划算法只需要多项式时间，从而获得较高的解题效率

2. 最优子结构

• 一个问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质
• 分析问题的最优子结构性质：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾
• 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解
• 最优子结构是一个问题能用动态规划算法求解的前提

3. 动态规划算法与分治算法的异同点

（1）动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题

（2）分治算法经分解得到的子问题往往是独立的

（3）动态规划算法经分解得到的子问题往往不是独立的，有些子问题被重复计算多次

4. 动态规划求解的基本步骤

（1）找出最优解的性质，并刻划其结构特征

（2）递归地定义最优值

（3）以自底向上的方式计算出最优值

（4）根据计算最优值时得到的信息，构造最优解

三、列举 7 个常见动态规划算法

列举 7 个常见动态规划算法练手，其余都在刷题篇！

1. 数字三角形

有一只小兔子站在一片三角形的胡萝卜地的入口，如右图所示，图中的数字表示每一个坑中胡萝

卜的数量，小兔子每次只能跳到左下角或者右下角的坑中，请问小兔子怎么跳才能得到最多数量

的胡萝卜？

1.1. 经典递归解法

实现代码：

public class Demo {public static void main(String[] args) {int[][] a = {{1},{3,2},{4,10,1},{4,3,2,20}};System.out.println(solve(a,0,0));}public static int solve(int[][] a,int i,int j){//第 n+1 层结束  ===》从0层开始计算 ，那么 i = n 时结束if (i == a.length){return 0;}return a[i][j]+ Math.max(solve(a,i+1,j),solve(a,i+1,j+1));}
}

1.2. 备忘录法

1. 详情见文章：【算法】备忘录法（记忆化搜索）
2. 上面递归时候，我们solve(a,2,1)被重复计算过两次，随着层数的增加，我们重复计算的子问题也会增加，为了避免重复计算子问题，我们就需要用到备忘录法，就是利用一个二维数组记录每次子问题计算的值，每次需要计算子问题时，先判断数组中是否计算过保存了，有的话直接用数组中结果，没有就计算并把结果保存到数组中。
3. 代码实现：

public class Demo {public static void main(String[] args) {int[][] a = {{1},{3,2},{4,10,1},{4,3,2,20}};System.out.println(solve(a,0,0,new int[a.length][a.length]));}public static int solve(int[][] a,int i,int j,int[][] p){//第 n+1 层结束  ===》从0层开始计算 ，那么 i = n 时结束if (i == a.length){return 0;}if (p[i][j] == 0) {p[i][j] = a[i][j] + Math.max(solve(a, i + 1, j, p), solve(a, i + 1, j + 1, p));}return p[i][j];}
}

1.3. 动态规划法

思路一

1. p[i][j]表示(i, j)的达到最后一层的最大路径和，那么p[i][j]的最优解包含了子问题p[i+1][j]或p[i+1][j+1]的最优解
2. 状态转移方程（递归方程）：

1. 图解：

1. 我们最终结果是p[0][0]
2. 动态规划法又叫填表法，填完上面那张表我们的结果就出来了
3. 实现代码：

public class Demo {public static void main(String[] args) {int[][] a = {{1},{3,2},{4,10,1},{4,3,2,20}};System.out.println(solve(a));}public static int solve(int[][] a){int[][] p = a.clone();//最后一层的数不需要修改 ，从倒数第二次开始for (int i = a.length -2; i >= 0; i--) {for (int j = 0; j <= i; j++) {p[i][j] = a[i][j] + Math.max(p[i+1][j],p[i+1][j+1]);}}return p[0][0];}
}

1. 通过代码可知时间复杂度O（n） = N ^ 2

思路二

1. p[i][j]表示从(1,1)到达(i, j) 的最大路径和，那么p[i][j]的最优解包含了子问题p[i-1][j-1]或p[i-1][j]的最优解
2. 状态转移方程（递归方程）：
3. 思路一就是从表的最后一层开始填，思路二是表的第一层开始填：

   

2. 最长公共子序列

2.1. 穷举搜索

2.2. 备忘录法

public class Blog {public static void main(String[] args) {//数组从1开始，舍弃0char[] x= {' ','A','C','D','E','D','C'};char[] y= {' ','A','B','C','D','C'};System.out.println(LCS(x, y, x.length-1, y.length-1, new int[x.length][y.length]));}/**** @param x 序列X* @param y 序列Y* @param i X下标* @param j Y下标* @param c 备忘录表* @return 最长子序列的长度*/public static int LCS(char[] x,char[] y,int i,int j,int[][] c){if (i == 0||j == 0){return  0;}if (c[i][j] == 0){if (x[i] == y[j]){c[i][j] = LCS(x,y,i-1,j-1,c)+1;}else {c[i][j] = Math.max(LCS(x,y,i-1,j,c),LCS(x,y,i,j-1,c));}}return c[i][j];}}

2.3. 动态规划

public class Blog {//测试：public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()){String line1 = scanner.nextLine();String line2 = scanner.nextLine();char[] chars1 = line1.toCharArray();char[] chars2 = line2.toCharArray();System.out.println(lcsLength(chars1, chars2));}}public static int lcsLength(char[] x,char[] y){int m = x.length;int n = y.length;//要填的表int[][] p = new int[m+1][n+1];//表的第1行和第一列全部为0for (int i = 0; i <= m; i++) {p[i][0]=0;}for (int i = 0; i <= n; i++) {p[0][i]=0;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (x[i-1]==y[j-1]){p[i][j] = p[i-1][j-1]+1;}else {p[i][j] = Math.max(p[i-1][j],p[i][j-1]);}}}return p[m][n];}}

package test.gaolang.blog3;import java.util.List;
import java.util.Scanner;/*** @author DELLHL*/
public class Blog {//测试：public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()){String line1 = scanner.nextLine();String line2 = scanner.nextLine();char[] chars1 = line1.toCharArray();char[] chars2 = line2.toCharArray();int[][] b = lcsLength(chars1, chars2, new int[chars1.length + 1][chars2.length + 1]);printlcs(chars1.length ,chars2.length ,chars1,b);System.out.println();}}public static int[][] lcsLength(char[] x,char[] y,int[][] b){int m = x.length;int n = y.length;int[][] p = new int[m+1][n+1];for (int i = 0; i <= n; i++) {p[0][i] = 0;}for (int i = 0; i <= m; i++) {p[i][0] = 0;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (x[i-1]==y[j-1]){b[i][j] = 1;p[i][j] = p[i-1][j-1]+1;}else if (p[i-1][j]>=p[i][j-1]){b[i][j] = 2;p[i][j] = p[i-1][j];}else {b[i][j] = 3;p[i][j] = p[i][j-1];}}}return b;}public static void printlcs(int i,int j, char[]a,int [][]drection) {if(i==0||j==0) {return;}if(drection[i][j]==1) {//下面两句代码的位置不能调换，调换就相当于逆序输出，全部递归完后，从第一个开始输出printlcs(i-1,j-1,a,drection);System.out.print(a[i-1]);}else if(drection[i][j]==2) {printlcs(i-1,j,a,drection);}else {printlcs(i,j-1,a,drection);}}
}

2.4. 改进

public class Blog {//测试：public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()){String line1 = scanner.nextLine();String line2 = scanner.nextLine();char[] chars1 = line1.toCharArray();char[] chars2 = line2.toCharArray();System.out.println(lcsLength(chars1, chars2));}}public static int lcsLength(char[] x,char[] y){int m = x.length;int n = y.length;//要填的表int[][] p = new int[2][Math.min(m,n)+1];//表的第1行和第一列全部为0for (int i = 0; i <= 1; i++) {p[i][0]=0;}for (int i = 0; i < Math.min(m,n); i++) {p[0][i]=0;}int flag = 0;for (int i = 1; i <= Math.max(m,n); i++) {flag = 1 - flag;for (int j = 1; j <= Math.min(m,n); j++) {if (x[i-1]==y[j-1]){p[flag][j] = p[1-flag][j-1]+1;}else {p[flag][j] = Math.max(p[1-flag][j],p[flag][j-1]);}}}return p[flag][Math.min(m,n)];}}

3. 最大子段和

public class Test {public static void main(String[] args) {int[] a = {-2,11,-4,13,-5,-2};System.out.println(solve(a));}public static int solve(int[] a){int[] p = new int[a.length];//以第一个结尾p[0] = a[0];int max = p[0];for (int i = 1; i < a.length; i++) {//从第二个开始if (p[i-1] > 0){p[i] = a[i] +p[i-1];}else {p[i] = a[i];}if (p[i] > max){max = p[i];}}return max;}
}

4. 最长公共子串

两个字符串，输出最长公共子串的长度。

4.1. 暴力法

public class Main {//公共子串public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//多组输入测试：while (scanner.hasNext()){String line = scanner.nextLine();String line2 = scanner.nextLine();char[] chars = line.toCharArray();char[] chars2 = line2.toCharArray();//记录最大长度int max = 0;//两个字符串，只要有一个为空，我们的长度为0，直接输出if (chars.length==0||chars2.length==0){System.out.println(0);}else {//以第一个字符for (int i = 0; i < chars.length; i++) {for (int j = 0; j < chars2.length; j++) {int m = i;int k = j;int len = 0;while(m < chars.length&&k <chars2.length&&chars[m]==chars2[k]){len++;m++;k++;}if (len > max){max = len;}}}System.out.println(max);}}}
}

4.2. 动态规划

public class Test2 {public static void main(String[] args) {String x = "acbcbcef";String y = "abcbced";System.out.println(LCS(x, y));}public static int LCS(String x,String y){char[] a = x.toCharArray();char[] b = y.toCharArray();int m = a.length;int n = b.length;int max = 0;int[][] p = new int[m+1][n+1];for (int i = 0; i <= m; i++) {p[i][0] = 0;}for (int i = 0; i <= n; i++) {p[0][n] = 0;}for (int i = 1; i < m+1; i++) {for (int j = 1; j < n+1; j++) {if (a[i-1]==b[j-1]){p[i][j] = p[i-1][j-1]+1;if (p[i][j] > max){max = p[i][j];}}else {p[i][j] = 0;}}}return max;}
}

如果要把这个公共子串输出，我可以在上面算法的基础上记录一下最大值的横坐标或者纵坐标。

public class Test2 {public static void main(String[] args) {String x = "acbcbcef";String y = "abcbced";System.out.println(LCS(x, y));}public static int LCS(String x,String y){char[] a = x.toCharArray();char[] b = y.toCharArray();int m = a.length;int n = b.length;int max = 0;int index = 0;int[][] p = new int[m+1][n+1];for (int i = 0; i <= m; i++) {p[i][0] = 0;}for (int i = 0; i <= n; i++) {p[0][n] = 0;}for (int i = 1; i < m+1; i++) {for (int j = 1; j < n+1; j++) {if (a[i-1]==b[j-1]){p[i][j] = p[i-1][j-1]+1;if (p[i][j] > max){max = p[i][j];index = i;}}else {p[i][j] = 0;}}}for (int i = max; i > 0; i--) {System.out.print(a[index-i]);}System.out.println();return max;}
}

5. 矩阵连乘

动态规划

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNextInt()){int n  = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}System.out.println(matrixChain(a, new int[a.length-1][a.length-1]));}}/*** 矩阵连乘* @param p 连乘矩阵* @param m  最小解*/public static int matrixChain(int[] p,int[][] m){//矩阵个数int n = p.length-1;//i=j的情况   m[i][i]:自有一个矩阵，没有乘法for (int i = 0; i < n; i++) {m[i][i] = 0;}//i < j的情况for (int i = 1; i < n; i++) {int k = i;for (int j = 0; j < n-i; j++) {//从j分开 m[j][j](=0)和m[j+1][k]  ,合并的乘法次数：p[j]xp[j+1]与p[j+1]xp[k+1]m[j][k] = m[j+1][k]+ p[j]*p[k+1]*p[j+1];//m[j][k] 从j+1开始分开，到k-1结束，选出乘法次数最少的for (int l = j+1; l < k; l++) {int t = m[j][l]+m[l+1][k] +p[j]*p[k+1]*p[l+1];if (t < m[j][k]){m[j][k] = t;}}k++;}}//m[0][n-1]:第一个矩阵到第n个矩阵连乘的最少次数return m[0][n-1];}
}

import java.util.Scanner;/*** @author DELLHL*/
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNextInt()){int n  = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}int[][] ints = matrixChain(a, new int[a.length - 1][a.length - 1], new int[a.length - 1][a.length - 1]);
/*            for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-1; j++) {System.out.print(ints[i][j]);}System.out.println();}*/traceback(ints,0,n-2);}}/*** 矩阵连乘* @param p 连乘矩阵* @param m  最小解* @param s 记录分割的值*/public static int[][] matrixChain(int[] p,int[][] m,int[][] s){//矩阵个数int n = p.length-1;//i=j的情况   m[i][i]:自有一个矩阵，没有乘法for (int i = 0; i < n; i++) {m[i][i] = 0;s[i][i] = 0;}//i < j的情况for (int i = 1; i < n; i++) {int k = i;for (int j = 0; j < n-i; j++) {//从j分开 m[j][j](=0)和m[j+1][k]  ,合并的乘法次数：p[j]xp[j+1]与p[j+1]xp[k+1]m[j][k] = m[j+1][k]+ p[j]*p[k+1]*p[j+1];s[j][k] = j;//m[j][k] 从j+1开始分开，到k-1结束for (int l = j+1; l < k; l++) {int t = m[j][l]+m[l+1][k] +p[j]*p[k+1]*p[l+1];if (t < m[j][k]){m[j][k] = t;s[j][k] = l;}}k++;}}return s;}public static void traceback(int[][] s,int i,int j){//只有一个矩阵 ==》结束if (i == j){return;}//[i,j]是从s[i][j]分开的，写成两个部分traceback(s,i,s[i][j]);traceback(s,s[i][j]+1,j);//因为我们i是从0开始的，所以 i和j输出时都需要加1，分开也是从0开始，比如s[i][j]=i表示分成[i][i]和[i+1][j]System.out.println("A["+(i+1)+":"+(s[i][j]+1)+"] * A["+(s[i][j]+2)+":"+(j+1)+"]");}
}

6. 最长递增子序列

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//多组测试while (scanner.hasNextInt()){//序列长度int n = scanner.nextInt();//序列int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}System.out.println(LIS(a));}}public static int LIS(int[] a){int[] dp = new int[a.length];int max = 1;for (int i = 0; i < a.length; i++) {//初始化为 1dp[i] = 1;//以 i结尾，最长递增序列长度for (int j = 0; j < i; j++) {if (a[j] < a[i]){if (dp[j] >= dp[i]){dp[i] = dp[j]+1;}}}if (dp[i] > max){max = dp[i];}}return max;}
}

import java.util.Scanner;
import java.util.Stack;public class Main3 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNextInt()){int n = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}LIS(a);}}public static int LIS(int[] a){int[] dp = new int[a.length];int[] pre = new int[a.length];int max_index = 1;int max = 1;pre[0] = -1;for (int i = 0; i < a.length; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (a[j] < a[i]){if (dp[j] >= dp[i]){dp[i] = dp[j]+1;pre[i] = j;}}}if (dp[i] > max){max = dp[i];max_index = i;}}Stack<Integer> stack = new Stack<>();//递增子序列最长时 最后一个元素为max_indexint index = max_index;while (index >= 0){//入栈stack.push(a[index]);//前一个下标index = pre[index];}int size = stack.size();for (int i = 0; i < size; i++) {//一一出栈System.out.print(stack.pop()+" ");}System.out.println();return max;}
}

7. 0-1背包问题

public class Knapsack {public static void main(String[] args) {//浪费数组的第一个int[] w = {0,2, 2, 6, 5, 4};int[] v = {0,6, 3, 5, 4, 6};System.out.println(fun(5, 10, v, w));}public static int fun(int n,int c,int[] v,int[] w){int[][] m = new int[n+1][c+1];//防止数组越界int jMax = Math.min(w[n]-1,c);//Step1:填最后一行//j<w[n] ==>m[n][j]=0for (int j = 0; j <= jMax; j++) {m[n][j] = 0;}//j>=w[n] ==>m[n][j]=v[n]for (int j = w[n]; j <= c; j++) {m[n][j] = v[n];}//Step2: 从倒数第二行往前面填for (int i = n-1; i > 1; i--) {jMax = Math.min(w[i]-1,c);for (int j = 0; j <= jMax; j++) {m[i][j] = m[i+1][j];}for (int j = w[i]; j <= c; j++) {m[i][j] = Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}}//第一行最后一个元素m[1][c] = m[2][c];if (c >= w[1]){m[1][c] = Math.max(m[1][c],m[2][c-w[1]]+v[1]);}return m[1][c];}
}

    //根据填的表格推断public static void traceback(int[][] m,int n,int c,int[] w){int[] x = new int[n+1];for (int i = 1; i < n; i++) {//没有选择if (m[i][c] == m[i+1][c] ){x[i] = 0;}else {x[i] = 1;c -= w[i];}}x[n] = (m[n][c]>0) ? 1:0;for (int i =1 ; i < x.length; i++) {System.out.print(x[i]+" ");}System.out.println();}