type
status
date
slug
summary
tags
category
icon
password
Hi there, this is Stephen speaking.
之前秋招笔试面试，发现很多大厂中厂都非常喜欢考察动态规划这一算法，于是对该算法做了一个整理总结，配合一些例题做了一些讲解。
1.一句话介绍算法特点
用空间换时间，基于一个递推公式和一个或多个初始状态的一种算法。
2.算法介绍
动态规划（Dynamic Programming，DP）是一种用于解决复杂问题的方法，特别适用于具有重叠子问题和最优子结构性质的问题。它通过将问题分解为更小的子问题来求解，避免重复计算，从而提高效率。
动态规划的基本思想
1.重叠子问题：问题可以分解为多个子问题，这些子问题会重复出现。例如，在计算斐波那契数时，f(n) = f(n-1) + f(n-2)，f(n-1) 和 f(n-2) 会在计算中多次出现。
2.最优子结构：一个问题的最优解可以由其子问题的最优解构成。如果一个问题的最优解依赖于其子问题的最优解，那么这个问题就具有最优子结构性质。
动态规划的步骤
1.定义状态：确定问题的状态，可以用一个数组或矩阵表示。
2.状态转移方程：找出状态之间的关系，定义状态转移方程，描述如何从一个状态转换到另一个状态。
3.初始条件：确定边界条件，通常是最小子问题的解。
4.计算顺序：根据状态转移方程计算出所有状态的值，通常是从小到大（自底向上）或从大到小（自顶向下）。
5.返回结果：根据需要，返回最终状态的值。
3.部分经典例题1.爬楼梯（leetcode70）
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
示例 2：
动态规划的入门题目，本质上可以抽象为斐波那契数列问题。f(n)=f(n-1)+f(n-2)，在所有爬法中，最后一步只有两种情况，f(n-1)和f(n-2)种，即最后一步爬两阶和最后一步爬一阶。由此我们仅需确定初始状态即可得该题目的动规解法（Pyhton3参考代码如下）
2.求最长公共子序列（leetcode1143）
给定两个字符串
text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
题解及注释
