二维动态规划

二维动态规划将相同的思想扩展到状态同时依赖于两个变量的问题中，通常是两个序列的索引或网格的两个维度。现在表格变成了矩阵，每个单元格根据其上方、左侧或对角相邻的单元格来填充。这里的问题包括字符串比较（编辑距离、最长公共子序列）、网格路径计数以及区间动态规划，你需要考虑区间而不是前缀。这些问题通常比一维动态规划更难设置，但一旦你确定了状态和转移，代码就可以直接从递推关系中得出。