动态规划笔记（贝尔曼算法）

动态规划满足最优化原理和无后效性

动态规划三种题型

1.计数

• 有多少种方式走到右下角
• 有多少种方法选出k个数使得和是Sum

2.求最大最小值

• 从左上角走到右下角路径的最大数字和
• 最长上升子序列长度

3.求存在性

• 取石子游戏,先手是否必胜
• 能不能选出k个数使得和是Sum

动态规划四个组成部分

1.确定状态

• 状态在动态规划中的作用属于定海神针

• 简单的说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么

  类似于解数学题中，X，Y，Z代表什么

• 确定状态需要两个意识:

  • 最后一步 保证最后一个问题减小规模问题不变，且结论不矛盾

  • 子问题：问题一样，规模变小

• 研究最优策略的最后一步化为子问题

2.转移方程

根据子问题直接得到

3.初始条件和边界条件

不重不漏（易说不易做 ）

4.计算顺序

自顶向下或自底向上，整体思路的体现，即能利用之前的结果进行计算，去掉重复计算的步骤

神奇的注意点（动规五部曲）

• dp数组以及下标的含义？二维一维数组中的i、j是什么意思
• 递推公式，不言而喻
• dp数组的初始化
• 遍历顺序（0/1背包问题为什么要先遍历背包后遍历物品，反过来是否可以；完全背包问题排列和组合for循环不同）
• 打印dp数组，用于debug，清晰思路

动态规划基本类型

1. 坐标型：dp数组下标为原来坐标，代表题型UniquePath
2. 序列型：dp数组下标为前i个，错开一个
3. 划分型：划分数组，每组满足一定性质
4. 区间型：用f[i][j]解决
5. 背包型：各种背包装载问题（区间）
6. 最长子序列型：dp数组下标为原来坐标，代表题型最长上升子序列
7. 博弈型：计算必胜或必败
8. 综合型：综合前面两种（如区间+博弈、动态+划分）或动态和其他算法（如动态+二分查找、动态+子母树 ）

动态规划时间空间优化

Follow Up常考

1. 滚动数组
2. 降维

动态规划打印路径（解）

动态规划基本题型

1. 动归基础
   • 斐波那契额数列
   • 爬楼梯问题
2. 背包问题
3. 打家劫舍
   • 树形dp（leetcode就三道题）
4. 股票问题
   • 买卖时间最大利润
5. 子序列问题
   • 最长子序列
   • 最长连续递增子序列
   • 编辑距离问题，两个字符串，最小编辑数使字符串相等。

拔尖类型题目，与我无关：区间dp、概率dp、