本文主要是介绍力扣hot100-动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 概念
- 动态规划
- 基本思想
- 常见步骤
- 常用技巧
- 常见问题类型
- 动态规划题目
- 题目: 爬楼梯
- 题解
概念
动态规划
动态规划
(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];}
我觉得这个题非常适合新手入门动态规划,这个题帮助新手掌握动态规划的核心思想,包括如何定义状态
、初始化状态
、如何进行状态转移
、如何处理边界条件
等
❤觉得有用的可以留个关注~❤
这篇关于力扣hot100-动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!