上篇主要是刷了两道真题(接龙数组和蜗牛 都是蓝桥杯2023的真题)有兴趣可以看看这个http://t.csdnimg.cn/AM9c2
分析思想:
这个事情就非常简单了 只需要把你的思想用代码实现就好了
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
的情况下的最大价值。通过嵌套循环迭代计算并更新每个状态的值,最终得到背包能够装载的最大价值。
动态背包 思想总结
好了本期先到这里 持续努力恶补算法中!