打卡打卡

2/12/2022
Unique Paths II
DP

2/12/2022
Knight Shortest Path II
DP
障碍物初始化为无穷大，x,y + 方向进行分治求和，通过打擂台找到和的最小值。分治自顶向下到最右下角。

2/13/2022
Jump Game
DP
一维

2/13/2022
背包
DP
求最优值，所以用DP可解，分治的思想
和坐标型动态规划稍有不同的是在于求和的思路做的是减法来表示添加

--------------------------

补充内容 (2022-02-15 16:51 +8:00):
对于dp - 当前状态是否满足和的表示方法，理解状态转移方程：要不要加当前的值，取决于上一个状态是否已经满足和了，或者加了当前值小于和，前提是和大于当前的值。如果和小于当前的值，肯定不加，直接继承方程的上一个状态。

加油楼主！

动态规划主要是状态转移方程，利用状态之间的抽象的关系省去重复计算，相比于深度优先搜索复杂度会降低

背包型动态规划是二维数组，状态可以为t/f，或者体积，或者价值，方程有01的问题，根据情况选择其一（可行性），最优值max + 加入体积或者价值。

Corgi03 发表于 2022-2-22 01:06
加油楼主！

ok. thank you.

3/5/2022
Word Break
DFS + Memo