![[Pasted image 20241109180506.png]]

数学归纳

动规是数学归纳的核心： 我们先假设这个结论在 k < n 时成立，然后根据这个假设，想办法推导证明出 k = n 的时候此结论也成立

子序列和子串

子序列：不一定连续 子串：一定连续

dp数组含义

dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

俄罗斯套娃信封（二维hard85/87，超时）

1.排序：先按宽度升序，后按高度降序

（因为宽度相同无法装，否则就升序了

2.标准LIS，比较高度的大小