广州企业网站建站,建设工程有限公司起名大全册子,湖北宜昌网络科技有限公司,注册网站需要营业执照吗#x1f389;#x1f389;欢迎光临#x1f389;#x1f389; #x1f3c5;我是苏泽#xff0c;一位对技术充满热情的探索者和分享者。#x1f680;#x1f680; #x1f31f;特别推荐给大家我的最新专栏《数据结构与算法#xff1a;初学者入门指南》#x1f4d8;欢迎光临 我是苏泽一位对技术充满热情的探索者和分享者。 特别推荐给大家我的最新专栏《数据结构与算法初学者入门指南》 希望能和大家一起学习共同进步 这是苏泽的个人主页可以看到我其他的内容哦 努力的苏泽http://suzee.blog.csdn.net 上篇主要是刷了两道真题接龙数组和蜗牛 都是蓝桥杯2023的真题有兴趣可以看看这个http://t.csdnimg.cn/AM9c2
进行讲解本篇讲解 动态规划的思想总结 真题实战答题模板哦~ 需要的伙伴们可以 收藏一下 目录
动态规划Dynamic Programming常常是蓝桥杯的常见考点 拿下他能够为比赛拉开不少的差距 于是专门开了两篇来写这个 这一篇主要是分析思想为主 分享遇到这类题要怎样去思考
动态规划的实现通常包括以下几个步骤
下面以一个经典的动态规划问题——「爬楼梯」为例进行说明
问题描述假设有一个n级的楼梯每次可以爬1级或2级求解爬到第n级楼梯的不同爬法总数。
下面分享一下我这段时间刷题总结出来的模板 如有失误请在评论区指出哦
一维动态规划
二维动态规划
动态背包
举一反三编辑动态背包 思想总结
这类应用于一类优化问题其中需要在给定的一组选择中做出最优决策以获得最大的收益或最小的成本可以通过以下步骤来思考和解决
我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code3e2vbc32adwko 动态规划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] 1dp[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[n1][W1]; // 初始化状态数组
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或没有物品可选时的情况。 填充状态表格根据定义的状态和状态转移方程可以创建一个二维表格或数组来存储中间结果。通过遍历状态表格并计算每个单元格的值填充整个表格。 求解最优解根据问题的要求可以从状态表格中读取最优解。例如如果问题要求最大价值则可以在表格的右下角找到最大值。 好了本期先到这里 持续努力恶补算法中 我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code3e2vbc32adwko
