上篇主要是刷了两道真题（接龙数组和蜗牛 都是蓝桥杯2023的真题）有兴趣可以看看这个http://t.csdnimg.cn/AM9c2
动态规划（Dynamic Programming）常常是蓝桥杯的常见考点 拿下他能够为比赛拉开不少的差距 于是专门开了两篇来写这个 这一篇主要是分析思想为主 分享遇到这类题要怎样去思考
动态规划的实现通常包括以下几个步骤：
- 定义问题的状态：将原问题划分为若干个子问题，同时定义每个子问题的状态。状态可以是原问题的某个维度的变量，如数组的索引、字符串的长度等。
- 确定状态转移方程：分析子问题之间的关系，找出状态之间的转移关系。这可以通过观察问题的特点和递推关系来得到。状态转移方程描述了如何根据已知状态计算下一个状态的值。
- 初始化边界状态：确定最简单的子问题的解，也就是边界状态的值。通常需要将边界状态的值预先计算或初始化为已知的值。
- 通过迭代计算：根据状态转移方程和边界状态，通过迭代计算解决子问题，并将中间结果存储起来。这样，在计算后续子问题时，可以直接利用已计算的结果，避免重复计算。
- 求解原问题：根据子问题的解，通过状态转移方程得到原问题的解。
下面以一个经典的动态规划问题——「爬楼梯」为例进行说明：
问题描述：假设有一个n级的楼梯，每次可以爬1级或2级，求解爬到第n级楼梯的不同爬法总数。
分析思想：
- 定义状态：令dp[i]表示爬到第i级楼梯的不同爬法总数。
- 状态转移方程：由于每次可以爬1级或2级，那么爬到第i级楼梯的爬法总数等于爬到第(i-1)级楼梯的爬法总数加上爬到第(i-2)级楼梯的爬法总数，即dp[i] = dp[i-1] + dp[i-2]。
- 边界状态：当楼梯级数为1时，只有一种爬法；当楼梯级数为2时，有两种爬法。即dp[1] = 1，dp[2] = 2。
- 迭代计算：根据状态转移方程和边界状态，通过迭代计算dp数组的值，从dp[3]开始计算，一直计算到dp[n]。
- 求解原问题：最终得到dp[n]即为爬到第n级楼梯的不同爬法总数。
这个事情就非常简单了 只需要把你的思想用代码实现就好了
public class ClimbingStairs { public static int climbStairs(int n) { if (n == 1) { return 1; } if (n == 2) { return 2; } int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } public static void main(String[] args) { int n = 4; int ways = climbStairs(n); System.out.println("The number of distinct ways to climb " + n + " stairs is: " + ways); } }
下面分享一下我这段时间刷题总结出来的模板 如有失误请在评论区指出哦
一维动态规划
int n = ...; // 输入规模 int[] dp = new int[n]; // 初始化状态数组 dp[0] = ...; // 初始化边界条件 for (int i = 1; i < n; i++) { // 状态转移方程 dp[i] = ...; } return dp[n-1]; // 返回最终结果
这种模板适用于一维动态规划问题，其中 dp[i] 表示第 i 个状态的值。通过迭代计算并更新每个状态的值，最终得到最优解。
二维动态规划
int m = ...; // 第一个维度的大小 int n = ...; // 第二个维度的大小 int[][] dp = new int[m][n]; // 初始化状态数组 dp[0][0] = ...; // 初始化边界条件 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 状态转移方程 dp[i][j] = ...; } } return dp[m-1][n-1]; // 返回最终结果
这种模板适用于二维动态规划问题，其中 dp[i][j] 表示第 (i, j) 个状态的值。通过嵌套循环迭代计算并更新每个状态的值，最终得到最优解。
动态背包
int n = ...; // 物品数量 int W = ...; // 背包容量 int[] weights = ...; // 物品重量数组 int[] values = ...; // 物品价值数组 int[][] dp = new int[n+1][W+1]; // 初始化状态数组 for (int i = 1; i <= n; i++) { int weight = weights[i-1]; int value = values[i-1]; for (int j = 1; j <= W; j++) { if (j < weight) { dp[i][j] = dp[i-1][j]; } else { dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight] + value); } } } return dp[n][W]; // 返回最终结果
这种模板适用于背包问题，其中 dp[i][j] 表示在前 i 个物品中选择，在背包容量为 j 的情况下的最大价值。通过嵌套循环迭代计算并更新每个状态的值，最终得到背包能够装载的最大价值。
举一反三动态背包 思想总结
这类应用于一类优化问题，其中需要在给定的一组选择中做出最优决策，以获得最大的收益或最小的成本可以通过以下步骤来思考和解决：
- 定义状态：首先，需要明确问题的状态。通常，状态与问题的限制条件有关。在动态背包问题中，状态可以定义为背包容量、可选择的物品、物品的数量等。
- 确定状态转移方程：接下来，需要找到状态之间的转移关系。也就是说，如何根据已知的状态来计算下一个状态。状态转移方程通常是通过观察问题的特点和约束条件得出的。
- 处理边界情况：在动态规划中，边界情况通常是最简单的子问题，其解是已知的或可以直接计算的。对于动态背包问题，边界情况可能是背包容量为0或没有物品可选时的情况。
- 填充状态表格：根据定义的状态和状态转移方程，可以创建一个二维表格或数组来存储中间结果。通过遍历状态表格并计算每个单元格的值，填充整个表格。
- 求解最优解：根据问题的要求，可以从状态表格中读取最优解。例如，如果问题要求最大价值，则可以在表格的右下角找到最大值。
