【冲击蓝桥篇】动态规划(下):你还在怕动态规划!?进来!答题模板+思路解析+真题实战

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 【冲击蓝桥篇】动态规划(下):你还在怕动态规划!?进来!答题模板+思路解析+真题实战

上篇主要是刷了两道真题(接龙数组和蜗牛 都是蓝桥杯2023的真题)有兴趣可以看看这个http://t.csdnimg.cn/AM9c2


动态规划(Dynamic Programming)常常是蓝桥杯的常见考点 拿下他能够为比赛拉开不少的差距 于是专门开了两篇来写这个 这一篇主要是分析思想为主  分享遇到这类题要怎样去思考


动态规划的实现通常包括以下几个步骤:


  1. 定义问题的状态:将原问题划分为若干个子问题,同时定义每个子问题的状态。状态可以是原问题的某个维度的变量,如数组的索引、字符串的长度等。
  2. 确定状态转移方程:分析子问题之间的关系,找出状态之间的转移关系。这可以通过观察问题的特点和递推关系来得到。状态转移方程描述了如何根据已知状态计算下一个状态的值。
  3. 初始化边界状态:确定最简单的子问题的解,也就是边界状态的值。通常需要将边界状态的值预先计算或初始化为已知的值。
  4. 通过迭代计算:根据状态转移方程和边界状态,通过迭代计算解决子问题,并将中间结果存储起来。这样,在计算后续子问题时,可以直接利用已计算的结果,避免重复计算。
  5. 求解原问题:根据子问题的解,通过状态转移方程得到原问题的解。


下面以一个经典的动态规划问题——「爬楼梯」为例进行说明:


问题描述:假设有一个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 的情况下的最大价值。通过嵌套循环迭代计算并更新每个状态的值,最终得到背包能够装载的最大价值。


举一反三动态背包 思想总结


这类应用于一类优化问题,其中需要在给定的一组选择中做出最优决策,以获得最大的收益或最小的成本可以通过以下步骤来思考和解决:


  1. 定义状态:首先,需要明确问题的状态。通常,状态与问题的限制条件有关。在动态背包问题中,状态可以定义为背包容量、可选择的物品、物品的数量等。


  1. 确定状态转移方程:接下来,需要找到状态之间的转移关系。也就是说,如何根据已知的状态来计算下一个状态。状态转移方程通常是通过观察问题的特点和约束条件得出的。


  1. 处理边界情况:在动态规划中,边界情况通常是最简单的子问题,其解是已知的或可以直接计算的。对于动态背包问题,边界情况可能是背包容量为0或没有物品可选时的情况。


  1. 填充状态表格:根据定义的状态和状态转移方程,可以创建一个二维表格或数组来存储中间结果。通过遍历状态表格并计算每个单元格的值,填充整个表格。


  1. 求解最优解:根据问题的要求,可以从状态表格中读取最优解。例如,如果问题要求最大价值,则可以在表格的右下角找到最大值。
相关文章
|
6天前
|
自然语言处理 编译器 Linux
|
11天前
|
Prometheus 监控 Cloud Native
实战经验:成功的DevOps实施案例解析
实战经验:成功的DevOps实施案例解析
26 6
|
8天前
|
UED
<大厂实战经验> Flutter&鸿蒙next 中使用 initState 和 mounted 处理异步请求的详细解析
在 Flutter 开发中,处理异步请求是常见需求。本文详细介绍了如何在 `initState` 中触发异步请求,并使用 `mounted` 属性确保在适当时机更新 UI。通过示例代码,展示了如何安全地进行异步操作和处理异常,避免在组件卸载后更新 UI 的问题。希望本文能帮助你更好地理解和应用 Flutter 中的异步处理。
58 3
|
8天前
|
JavaScript API 开发工具
<大厂实战场景> ~ Flutter&鸿蒙next 解析后端返回的 HTML 数据详解
本文介绍了如何在 Flutter 中解析后端返回的 HTML 数据。首先解释了 HTML 解析的概念,然后详细介绍了使用 `http` 和 `html` 库的步骤,包括添加依赖、获取 HTML 数据、解析 HTML 内容和在 Flutter UI 中显示解析结果。通过具体的代码示例,展示了如何从 URL 获取 HTML 并提取特定信息,如链接列表。希望本文能帮助你在 Flutter 应用中更好地处理 HTML 数据。
91 1
|
11天前
|
自然语言处理 编译器 Linux
告别头文件,编译效率提升 42%!C++ Modules 实战解析 | 干货推荐
本文中,阿里云智能集团开发工程师李泽政以 Alinux 为操作环境,讲解模块相比传统头文件有哪些优势,并通过若干个例子,学习如何组织一个 C++ 模块工程并使用模块封装第三方库或是改造现有的项目。
|
14天前
|
人工智能 资源调度 数据可视化
【AI应用落地实战】智能文档处理本地部署——可视化文档解析前端TextIn ParseX实践
2024长沙·中国1024程序员节以“智能应用新生态”为主题,吸引了众多技术大咖。合合信息展示了“智能文档处理百宝箱”的三大工具:可视化文档解析前端TextIn ParseX、向量化acge-embedding模型和文档解析测评工具markdown_tester,助力智能文档处理与知识管理。
|
22天前
|
架构师 关系型数据库 MySQL
MySQL最左前缀优化原则:深入解析与实战应用
【10月更文挑战第12天】在数据库架构设计与优化中,索引的使用是提升查询性能的关键手段之一。其中,MySQL的最左前缀优化原则(Leftmost Prefix Principle)是复合索引(Composite Index)应用中的核心策略。作为资深架构师,深入理解并掌握这一原则,对于平衡数据库性能与维护成本至关重要。本文将详细解读最左前缀优化原则的功能特点、业务场景、优缺点、底层原理,并通过Java示例展示其实现方式。
50 1
|
23天前
|
机器学习/深度学习 人工智能 算法
揭开深度学习与传统机器学习的神秘面纱:从理论差异到实战代码详解两者间的选择与应用策略全面解析
【10月更文挑战第10天】本文探讨了深度学习与传统机器学习的区别,通过图像识别和语音处理等领域的应用案例,展示了深度学习在自动特征学习和处理大规模数据方面的优势。文中还提供了一个Python代码示例,使用TensorFlow构建多层感知器(MLP)并与Scikit-learn中的逻辑回归模型进行对比,进一步说明了两者的不同特点。
54 2
|
25天前
|
JavaScript 调度
Vue事件总线(EventBus)使用指南:详细解析与实战应用
Vue事件总线(EventBus)使用指南:详细解析与实战应用
41 1
|
5天前
|
前端开发 JavaScript
JavaScript新纪元:ES6+特性深度解析与实战应用
【10月更文挑战第29天】本文深入解析ES6+的核心特性,包括箭头函数、模板字符串、解构赋值、Promise、模块化和类等,结合实战应用,展示如何利用这些新特性编写更加高效和优雅的代码。
14 0

推荐镜像

更多