概念
动态规划
动态规划（Dynamic Programming，简称DP）是一种解决问题的算法思想，通常用于优化问题。它的核心思想是将一个大问题分解成若干个子问题，并通过保存子问题的解来避免重复计算，从而提高效率。
基本思想
-
优化子结构：动态规划适用于那些可以将问题分解为子问题的问题，且这些子问题的解可以用来构建原问题的解。也就是说，问题具有重叠子问题的性质。
-
最优子结构：原问题的最优解可以由子问题的最优解组合而成。即，如果子问题的解是最优的，那么它们的组合也能构成原问题的最优解。
常见步骤
-
定义状态：
确定DP数组（或表）中的状态代表什么。状态通常是对问题的某一方面的描述，可以是一个数组或矩阵中的一个元素。 -
确定状态转移方程：
找出状态之间的关系，通常是用来从一个状态计算出另一个状态的公式或规则。 -
初始化状态：
设置边界条件，通常是最简单的情况或基础情况的解。例如，数组的第一个元素或最小子问题的解。 -
填充DP表：
根据状态转移方程从初始状态开始，逐步计算出所有状态的解，直到得到原问题的解。 -
返回结果：
最终的解通常会保存在DP表的某个位置，根据问题的要求返回相应的值。
常用技巧
-
空间优化：
如果DP表的某一行或某一列只依赖于前一行或列，可以只保留当前行（或列）的状态，减少空间复杂度。例如，二维DP数组可以优化为一维数组。 -
状态压缩：
如果状态转移只依赖于有限个先前状态，可以使用状态压缩技巧将二维状态数组转为一维数组。 -
递推和备忘录：
递归方法与动态规划结合称为备忘录法（Memoization），通过缓存已经计算过的子问题的结果来避免重复计算。 -
按序计算：
按照状态转移的依赖顺序填充DP表，确保计算某一状态时其依赖的状态已经计算完毕。 -
重叠子问题：
动态规划特别适用于存在重叠子问题的情况，即问题可以被分解为多个相同的子问题，这些子问题的解在不同的计算中被多次使用。
常见问题类型
-
路径问题：
比如“最短路径”或“最长路径”，如网格最短路径、背包问题等。 -
选择问题：
比如“选择某些元素使得总和最大”，如背包问题、股票买卖问题等。 -
字符串问题：
如“编辑距离”、“最长公共子序列”、“字符串匹配”等。 -
序列问题：
比如“最大子序列和”、“最长递增子序列”等。
动态规划题目
题目： 爬楼梯
原题链接： 爬楼梯
题解
爬楼梯问题的动态规划解法的步骤如下：
-
定义状态：
dp[i]表示到达第i层楼梯的方案数。 -
初始化状态：
dp[0] = 1：表示在第0层（即不爬楼梯）只有一种方式，即什么都不做。dp[1] = 1：表示只有一种方式到达第1层，即一步到达。
-
状态转移方程：
dp[i] = dp[i - 1] + dp[i - 2]：到达第i层的方案数等于到达第i-1层的方案数加上到达第i-2层的方案数。因为从第i-1层可以一步到达第i层，从第i-2层可以两步到达第i层。
-
填充DP表：
- 从
i = 2开始，逐步计算到达每一层的方案数，并存储在dp数组中。
- 从
public static int climbStairs(int n) {// 定义状态int[] dp = new int[n + 1];// dp[i]表示爬到第i层楼梯的方案数// 初始状态dp[0] = 1;dp[1] = 1;// 状态转移方程 dp[i] = dp[i-1]+dp[i-2];for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}我觉得这个题非常适合新手入门动态规划，这个题帮助新手掌握动态规划的核心思想，包括如何定义状态、初始化状态、如何进行状态转移、如何处理边界条件等
❤觉得有用的可以留个关注~❤
