DP 路径 - wenzhoullq/leetcode GitHub Wiki
路径DP一定要先初始化,即对dp赋值-1,然后递推路径的时候需要上一层不为-1,易错点
右下行走路径
分析
关键词是右下/左上行走(如果是四个方向行走的话则是dfs了),并且起点是(0,0)或则(y,x);
题目
174. 地下城游戏这个存在着资源消耗,但是从右下往左上走的话就可以降维了
1301. 最大得分的路径数目 其实这是道简单题,不存在着资源消耗的说法,每次更新dp的时候更新f即可
1463. 摘樱桃 II 主要在于初始化,易漏
1594. 矩阵的最大非负积(老老实实按照原版初始化好了)
向下行走路径
分析
关键词是向下行走
记忆化dfs/资源消耗型
分析
指的是既可以用记忆化dfs又可以用dp的题,其中分为资源消耗型,资源消耗可以是显性已经告知的资源,也可能是运行中形成的约束