动态规划知识点
我也不知道为啥要收fei，我普通上传，但是平台好像不能直接看，大家可以试看，因为该文档就两页，还没完善
1.动态规划与贪心的区别
（1）求解问题区别：
贪心：
顾名思义，就是尽量的贪心使得结果利益最大化，从局部最优推出全局最优，比如：桌子上有三张钞票，面额各不相同，你只能取两次，每次只能取一张，那样子怎么取呢？
很明显，就是每次取所有钞票种面额最大的一张
这里的局部最优：每次取的时候的最大面额
全局最优：使得结果最大
动态规划：
简称dp，如果一个问题有很多重叠子问题，那么用动态规划是最有效的。所以动态规划是需要从上一个状态推出后面状态的（和贪心最大的区别），这也就是为什么dp解题都有一个公式，这个公式叫递推公式。递推公式很重要，其实最重要的还有其他几点，等下说。
2.动态规划经典题型
动态规划是一种解决优化问题的算法思想，它可以解决许多不同类型的问题，包括但不限于以下几种：
最短路径问题：在一个有向图或者无向图中，找到两个节点之间最短路径的长度。（dp[i][j]：存到该点的最小路径）
最长公共子序列问题：给定两个序列，找到它们最长的公共子序列的长度。
最大子数组和问题：给定一个整数数组，找到一个连续子数组，使得该子数组的和最大。
最长递增子序列问题：给定一个序列，找到一个最长的递增子序列的长度。
简单题：
爬楼梯，斐波那契数列数列
（题解链接：
爬楼梯：LeetCode 爬楼梯（动态规划题解）-CSDN博客
斐波那契数列：斐波那契数列规划题题解-CSDN博客）
中等：
四种背包（01背包，完全背包，多重背包，分组背包），打家劫舍，
买卖股票的最佳时机，最长公子序列，最长递增子序列（题解链接：LeetCode 300. 最长递增子序列 题解（C,C++） （包含动态规划与贪心的区别的资料）-CSDN博客），最长连续递增子序列，最长重复子数组，最大子序和
背包：（我之前的题解中有一维写法哦，二维写法空间复杂度较高，因此我并未使用，一维写法：01背包 与 emo题目背景（周超人的遗憾） 的爱恨情仇-CSDN博客）
它二维数组是dp[i][j]，从0到i这些物品里面选，背包容量为j，dp[i][j]的意思是它能装下的最大价值
3.动态规划最重要的五步：
（1）确定dp数组及下标的含义（dp[i]）
（2）确定递推公式
（3）确定如何初始化
（4）确定遍历顺序
（5）打印数组
标签：知识点,背包,题解,文档,序列,动态,规划,dp From： https://blog.csdn.net/2301_79293429/article/details/136806858