摘要本文系统讲解动态规划的核心思想并以经典的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选价值最大的策略。手把手全流程教学第①步先处理边界当i0即物品数量为0此时没物品可选所以最大价值为0故第一行全是0当j0即背包容量为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[N1][W1]; //开始循环填充DP数组二维表格 for(int i1; iN; i){ for(int j1; jW; j){ //每个格子都要考虑 选/不选 当前物品并且取二者的价值较大者填入当前格子 if(jw[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④官方答案以上就是本篇文章的全部内容喜欢的话可以留个免费的关注呦~~~