“这是我参与8月更文挑战的第17天，活动详情查看： 8月更文挑战”

这篇文章大概是四五月份开始写的，后来忙于毕业就一直忘了写🤣。这几天刚好有时间把这篇文章收收尾，如果觉得有用就点个赞吧！

注： 本文21道动态规划相关的LeetCode题目节选自CodeTop中考察频率较高的动态规划题目，文章较长，全文约15000字，可以收藏一波嗷~~

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，而我们希望找到具有最优值的解。动态规划算法与分治法类似，基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

动态规划问题经分解得到的子问题往往不是互相独立的。需要保存已解决的子问题的答案，而在需要时再找出已保存的答案，这样就可以避免大量的重复计算。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

动态规划有两个重要的概念：

动态规划解题步骤：

下面就通过爬楼梯问题来看看动态规划的具体应用。

题目描述：假设正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？其中 n 是一个正整数。

示例 1：

示例 2：

这道题有两个关键特征：

这样的问题往往可以用动态规划进行求解。对于这个问题，每次爬楼梯只有两种情况：

f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2)，这就是本题用到的递推关系。下面就根据动态规划的四个步骤来看那一下：

动态规划实现代码如下：

示例 3：

示例 4：

提示：

示例 2：

提示：