动态规划入门指南

动态规划入门指南

动态规划是一种解决复杂问题的方法，它可以将一个问题分解为若干个子问题，并利用子问题的最优解来构造原问题的最优解。动态规划适用于具有重叠子问题和最优子结构的问题，即子问题之间有相互依赖的关系，且子问题的最优解可以推导出原问题的最优解。

本文将介绍动态规划的基本概念、常见模式、解题框架和学习路线，并给出一些练习题目和参考链接，希望对你有所帮助。

基本概念

动态规划和分治算法都是基于将原问题分解为子问题，并通过组合子问题的解来得到原问题的解。不同的是，动态规划要求原问题具有以下两个特性：

• 重叠子问题：原问题可以分解为若干个子问题，而这些子问题中有很多是相同或相似的，不需要重复计算，可以将其结果保存起来。
• 最优子结构：原问题的最优解可以由其子问题的最优解组合而成，即子问题之间相互独立，不影响最终结果。

动态规划有两种基本的实现方式：

• 自顶向下：也称为记忆化递归，即从原问题出发，递归地求解子问题，并将已经求解过的子问题的结果保存在一个数组或哈希表中，避免重复计算。
• 自底向上：也称为递推或迭代，即从最简单的子问题开始，逐步推导出更复杂的子问题的解，并将其保存在一个数组或哈希表中，最后得到原问题的解。

动态规划的核心是找出状态和状态转移方程。状态是指原问题和子问题中变化的量，用来描述问题的不同阶段。状态转移方程是指如何从一个或多个已知状态推导出另一个状态的关系式，用来描述问题之间的联系。

动态规划的常见模式

动态规划可以应用于不同类型和难度的问题，但是它们往往有一些共同的模式或套路。以下是一些常见的动态规划模式：

• 数塔：数塔是一个由数字组成的三角形矩阵，要求从顶部走到底部，每一步只能走到相邻的位置，求出路径上数字之和最大或最小值。例如：118. 杨辉三角、120. 三角形最小路径和等。
• 斐波那契数列：斐波那契数列是一个由0和1开始，后面每一项都等于前两项之和的数列。例如：509. 斐波那契数、1137. 第 N 个泰波那契数等。
• 爬楼梯：爬楼梯是一个经典的动态规划模型，要求在给定阶梯数和每次可爬的阶数的情况下，求出爬到顶部的方法数或最小花费。例如：70. 爬楼梯、746. 使用最小花费爬楼梯等。
• 偷房子：偷房子是一个涉及到选择和限制的动态规划模型，要求在给定一排房屋和每个房屋的价值的情况下，求出能够偷窃到的最高总价值，同时不能偷相邻的房屋。例如：198. 打家劫舍、213. 打家劫舍 II等。
• 0/1背包：0/1背包是一个涉及到选择和容量的动态规划模型，要求在给定一组物品和每个物品的重量和价值的情况下，求出能够装入背包的最大价值，同时不能超过背包的容量。例如：416. 分割等和子集、494. 目标和等。

动态规划的解题框架

动态规划的解题步骤一般如下：

• 定义状态：确定问题中变化的量，并用一个或多个变量来表示。例如，斐波那契数列中变化的量是第n个数，可以用n来表示状态；爬楼梯中变化的量是第n阶楼梯，可以用n来表示状态。
• 定义状态转移方程：确定问题中不变的量，并用一个或多个公式来表示状态之间的关系。例如，斐波那契数列中不变的量是每个数等于前两个数之和，可以用f(n) = f(n-1) + f(n-2)来表示状态转移方程；爬楼梯中不变的量是每次可以爬1或2阶，可以用f(n) = f(n-1) + f(n-2)来表示状态转移方程。
• 确定边界条件：确定问题中已知或特殊的状态，并给出其对应的值。例如，斐波那契数列中已知的状态是f(0) = 0, f(1) = 1；爬楼梯中已知的状态是f(0) = 1, f(1) = 1。
• 实现算法：根据自顶向下或自底向上的方式，利用状态转移方程和边界条件，实现动态规划算法。一般来说，自顶向下需要使用递归和备忘录，自底向上需要使用迭代和数组。

动态规划的学习路线

动态规划是一种需要多练多思考才能掌握的方法，建议按照以下步骤进行学习：

• 首先了解动态规划的基本概念、特点和原理，掌握动态规划的解题框架和思维方式。
• 其次从简单到困难，按照不同类型和模式，练习一些典型和经典的动态规划题目，总结其中的套路和技巧。
• 最后不断巩固和提高动态规划的能力，尝试解决一些更复杂和更有挑战性的动态规划题目，拓展自己的思路和视野

动态规划的练习题目

以下是一些动态规划的练习题目，按照不同的类型和难度进行了分类，你可以根据自己的水平和进度来选择合适的题目进行练习。每个题目都附有链接，你可以点击查看题目详情和解答。

数塔

• 118. 杨辉三角（简单）
• 119. 杨辉三角 II（简单）
• 64. 最小路径和（中等）
• 120. 三角形最小路径和（中等）
• 931. 下降路径最小和（中等）
• 1289. 下降路径最小和 II（困难）
• 1301. 最大得分的路径数目（困难）

斐波那契数列

• 509. 斐波那契数（简单）
• 1137. 第 N 个泰波那契数（简单）
• 70. 爬楼梯（简单）
• 746. 使用最小花费爬楼梯（简单）

偷房子

• 198. 打家劫舍（简单）
• 213. 打家劫舍 II（中等）
• 337. 打家劫舍 III（中等）

0/1背包

• 416. 分割等和子集（中等）
• 494. 目标和（中等）
• 1049. 最后一块石头的重量 II（中等）
• 474. 一和零（中等）

完整题目 参照：

动态规划的总结和心得

动态规划是一种非常强大和实用的算法思想，它可以帮助我们解决很多看似复杂的问题，提高我们的编程能力和思维水平。但是动态规划也是一种需要不断练习和总结的方法，它并不是一种固定的套路，而是一种灵活的思维方式。

学习动态规划的过程中，我有以下几点心得：

• 要有耐心和信心，不要轻易放弃。动态规划的题目往往有一定的难度和抽象性，一开始可能会感到困惑和无从下手，但是只要坚持不懈地思考和练习，就会有所收获和进步。
• 要善于归纳和总结，找出问题的本质和规律。动态规划的题目虽然形式各异，但是它们都有一些共同的特点和模式，例如重叠子问题、最优子结构、状态定义、状态转移方程等。通过归纳和总结这些特点和模式，可以帮助我们更快地理解和掌握动态规划的思想和方法。
• 要多角度和多层次地思考，寻找问题的最优解。动态规划的题目往往有多种解法，其中有些解法可能更优雅、更高效、更简洁。通过多角度和多层次地思考问题，可以帮助我们找出问题的最优解，并且提高我们的编程技巧和代码质量。

动态规划的参考链接

以下是一些关于动态规划的参考链接，你可以通过阅读这些文章来加深对动态规划的理解和掌握。

• 「动态规划」问题特性、解题框架、练习例题 - 力扣（LeetCode）：这篇文章介绍了动态规划的问题特点，和分治算法的联系与区别，以及动态规划的解题框架和练习例题。文章中给出了一些常见的动态规划问题的类型，例如数塔、斐波那契数列、爬楼梯、偷房子等，并给出了相应的代码实现。
• leetcode动态规划题目总结 - 力扣（LeetCode）：这篇文章是一个中国程序员根据自己的学习经验总结的动态规划题目清单。文章中按照不同的主题，列出了一些典型的动态规划问题，例如0/1背包、相等子集划分、子集和、记忆化搜索等，并给出了相应的链接和难度等级。
• 「动态规划」 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台：这是一个官方提供的动态规划学习计划，包含了一些基础和进阶的动态规划问题，以及相关的视频讲解和参考资料。学习计划中按照不同的主题，给出了一些推荐的动态规划问题，例如最长递增子序列、最长公共子序列、最大子数组和、最长回文子序列等。
• 动态规划 - 维基百科，自由的百科全书
• 动态规划 - 算法与数据结构 - 极客学院Wiki
• 动态规划详解 - labuladong的算法小抄 - 知乎专栏
• 动态规划入门到放弃 - 算法小抄 - 知乎专栏