企业官网建设流程全解析

摘要

本文系统讲解动态规划的核心思想，并以经典的01背包问题为例进行手把手教学。文章从解法思路入手，详细拆解DP表格中每个格子的含义、填表顺序以及"选与不选"两种策略的推导过程，配合完整的Java代码实现，帮助读者直观理解动态规划的填表逻辑。此外，文章还结合力扣实战刷题与软考真题，提供题目分析、解题思路与官方答案，适合备考软考及算法入门的读者学习参考。

核心思想

• 选当前物品：最大价值 = 当前选中的物品的价值 + 剩余背包容量去上一行发挥出的最大价值

• 不选当前物品：最大价值 = 上方相邻格子的价值

每一个格子，我们都需要考虑上方两种情况，并且取值 max（策略1， 策略2），选价值最大的策略。

目录

一、动态规划的基本思想

二、动态规划的典型例子—01背包问题

解法思路

每个格子的值的含义

填写表格的顺序

两个策略

手把手全流程教学

代码实现

力扣实战刷题

软考真题

2019—下半年—试题四

①题目

②问题

③分析

④官方答案

2021—下半年—试题四

①题目

②问题

③分析

④官方答案

一、动态规划的基本思想

二、动态规划的典型例子—01背包问题

①“01”的概念：一个物品，要么装进背包、要么不装。

解法思路

要想解决原问题，就先解决子问题（这句话是动态规划的核心思想）。

大白话：

• 你不是要求物品数量是4吗，那我就先求出物品数量是3的最大价值、物品数量是2的最大价值、物品数量是1的最大价值、物品数量是0的最大价值。
• 你不是要求背包容量是5吗，那我就先求出背包容量是4的最大价值、背包容量是3的最大价值、背包容量是2的最大价值、背包容量是1的最大价值、背包容量是0的最大价值。

从上面两个维度，可以求出子问题，然后通过子问题，最终求解原问题。这就是动态规划的魅力。

然后上述两个维度的缩放，可以画成下面的一张二维数组表格。

每个格子的值的含义

每个格子的值，就是对应的情况的最大价值。

举例：

下图红框的值，即2，就是当物品数量为1、背包容量为1时的最大价值。其他值也同理。

填写表格的顺序

从上到下，一行一行的来。

两个策略

• 选当前物品：最大价值 = 当前选中的物品的价值 + 剩余背包容量去上一行发挥出的最大价值

• 不选当前物品：最大价值 = 上方相邻格子的价值

每一个格子，我们都需要考虑上方两种情况，并且取值 max（策略1， 策略2），选价值最大的策略。

手把手全流程教学

第①步：先处理边界

• 当i=0（即物品数量为0），此时没物品可选，所以最大价值为0，故第一行全是0
• 当j=0（即背包容量为0），此时啥都装不下，所以最大价值为0，故第一列全是0

第②步：根据上面的策略（选当前物品/不选当前物品，哪个策略的价值大就填充哪个值）

代码实现

public class test01 { public static void main(String[] args) { //先定义题目描述的东西 int N = 4;//原问题的物品数量：4个 int W = 5;//原问题的背包容量：5 int v[] = {0, 2, 4, 5, 6};//第0~4个物品的价值 int w[] = {0, 1, 2, 3, 4};//第0~4个物品的重量 //定义待填充的二维数组表格（专业术语叫dp数组） int[][] f = new int[N+1][W+1]; //开始循环，填充DP数组（二维表格） for(int i=1; i<=N; i++){ for(int j=1; j<=W; j++){ //每个格子，都要考虑 选/不选 当前物品，并且取二者的价值较大者，填入当前格子 if(j>=w[i]){ f[i][j] = Math.max(f[i-1][j], v[i]+f[i-1][j-w[i]]); }else{ f[i][j] = f[i-1][j]; } } } //输出结果，最大价值就是f[N][W]的值(即DP数组右下角的那个格子的值) System.out.println("最大价值："+f[N][W]); } }

运行结果：

可见此时没问题。

我们还可以将DP数组打印出来，看看和我们之前手动填充的表格一致吗？

//打印出DP数组 for (int i = 0; i <= N; i++) { // 内层循环控制列 (j)，从 0 到 W for (int j = 0; j <= W; j++) { // 打印当前格子的值，使用 \t (制表符) 分隔，使对齐更美观 System.out.print(f[i][j] + "\t"); } // 【关键】每一行打印完后，输出一个换行符 System.out.println(); }

可见此时，通过程序跑出的结果，和我们之前手动推导的一模一样。

力扣实战刷题

动态规划_01背包问题_携带研究材料-CSDN博客

软考真题

2019—下半年—试题四

①题目

②问题

③分析

④官方答案

2021—下半年—试题四

①题目

②问题

③分析

红框解读：
红框这两个for循环，是在初始化dp数组

具体含义：

此时含义是：当目前两个字符相等，那么无需任何操作，步数不变（即：无需进行增、删、改）

如果这道题你不确定是str1[i-1] = str2[j-1] 还是 str1[i] = str2[j]的话，此时我们要会灵活运用题目给的线索

可见此时肯定是i-1和j-1是正确的下标。

这个空，其实题目也早就给了，如下图：

意思是，当目前两个字符不相等时，我们要将两个字符串变成一致的，策略就是采取增、删、改三个操作中，步数最小的那一个。所以用了min函数。

其实这个空也非常简单，我们所求的最终答案，就是dp数组的右下角那个元素，也即：d[len1][len2]

动态规划算法，这很明显了，不多解释。

至于这个算法的时间复杂度，分析如下：

由于算法的时间复杂度，是取决于那个最长的循环，所以该算法的时间复杂度为O(mn)

将第一个字符串：删掉T、增加A、增加C、增加T。

经过上面的四步，就能变成第二个字符串。

所以编辑距离 = 4

④官方答案

以上就是本篇文章的全部内容，喜欢的话可以留个免费的关注呦~~~