一、动态规划基本原理

1. 理解动态规划

动态规划（Dynamic Programming, DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的*。这些子问题之间通常是重叠的，即一个子问题的解可能会被多个子问题所使用。

2. 动态规划的三个特征

• *子结构：原问题的*解包含其子问题的*解。
• 无后效性：即某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。
• 重复子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

二、力扣上的动态规划解题思路

1. 定义子问题

将原问题分解成若干个规模较小的子问题，并定义这些子问题的解。子问题通常是参数化的，可以通过递归或迭代的方式求解。

2. 状态转移方程

找到子问题之间的递推关系，即状态转移方程。这是动态规划解题的核心，通过状态转移方程可以计算出所有子问题的解，并最终得到原问题的解。

3. 初始化与边界条件

在求解过程中，需要初始化一些基本的状态，并处理好边界条件。这些基本状态和边界条件是递推计算的起点，必须保证正确无误。

4. 递推计算

根据状态转移方程，通过递推或迭代的方式计算出所有子问题的解。在计算过程中，需要利用已经计算出的子问题的解来求解当前子问题的解。

5. 返回结果

当所有子问题的解都计算完成后，就可以根据原问题的定义返回最终结果了。

三、力扣上的动态规划学习路径

1. 基础题目练习

初学者可以从力扣上的基础动态规划题目开始练习，如斐波那契数列、爬楼梯等。这些题目相对简单，但涵盖了动态规划的基本概念和解题思路。

2. 进阶题目挑战

在掌握了基础动态规划题目后，可以挑战一些进阶题目，如背包问题、打家劫舍、股票买卖等。这些题目需要更深入地理解动态规划的原理和技巧，并能够灵活运用状态转移方程进行求解。

3. 深入理解与总结

在解题过程中，要注重对动态规划原理的深入理解和对解题技巧的总结。可以通过阅读相关书籍、博客和教程等方式加深对动态规划的理解，并学会将所学知识应用到实际问题中去。

4. 实战演练

*，要通过大量的实战演练来巩固所学知识并提高解题能力。可以参加力扣上的比赛或挑战赛来检验自己的水平，并与其他选手交流学习心得和技巧。

四、示例题目分析

以力扣上的“打家劫舍”题目为例，该题目要求在一个由非负整数组成的数组中，你扮演一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的*制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的*金额。

解题思路：

• 定义子问题：f(k) 表示偷前 k 个房子能够得到的*金额。
• 状态转移方程：f(k) = max(f(k-1), nums[k-1] + f(k-2))，其中 nums[k-1] 表示第 k 个房子的金额。
• 初始化与边界条件：f(0) = 0（没有房子可偷），f(1) = nums[0]（只有一个房子可偷）。
• 递推计算：从 f(2) 开始递推计算每个 f(k) 的值，直到计算出 f(n)（n 为数组长度）。
• 返回结果：返回 f(n) 即为所求的*金额。