【冲击蓝桥篇】动态规划（下）：你还在怕动态规划！？进来！答题模板+思路解析+真题实战

��欢迎光临

我是苏泽，一位对技术充满热情的探索者和分享者。

特别推荐给大家我的最新专栏《数据结构与算法：初学者入门指南》

希望能和大家一起学习！共同进步！

这是苏泽的个人主页可以看到我其他的内容哦

努力的苏泽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_code=3e2vbc32adwko

---

动态规划（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