#学习笔记

##高级动态规划

###一、递归、分治、动态规划复习

动态规划：适合有重复子问题的情况，其思想为分治加上最优子结构，通常使用顺推形式进行动态递推。

动态规划/分治/递归的共性是：找到重复子问题。

差异性：动态规划需要找到最优子结构，并在中途淘汰次优解。

###二、进阶版动态规划 动态规划问题的复杂度来源是状态定义和状态转移方程。

• 状态拥有更多维度（二维、三维或者更多，甚至需要压缩）。
• 状态转移方程更加复杂。
• 本质：内功、逻辑思维、数学。

###三、不同路径 II 的状态转移方程

状态表示：创建包含m行和n列的二维数组 dp，其中 dp[i][j] 表示从左上角到位置 (i, j) 的不同路径数。

边界情况：由于每步只能往下或往右，因此 dp 的第一行和第一列（指下标为0的行和列）的值为1或0。从左到右遍历第一行，如果没有障碍物，则对应的 dp 值为1，一旦遇到障碍物，则第一行从这个位置开始向右的全部元素对应的 dp 值都为0。从上到下遍历第一列，如果没有障碍物，则对应的 dp 值为1，一旦遇到障碍物，则第一列从这个位置开始向下的全部元素对应的 dp 值都为0。

状态转移方程：当 i > 0 且 j > 0 时，首先判断位置 (i, j) 是否为障碍物，如果为障碍物则 dp[i][j] = 0，如果不为障碍物则位置 (i, j) 可由位置 (i - 1, j) 下移一步到达或者由位置 (i, j - 1) 右移一步到达，因此 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

因此状态转移方程分解为如下两种情况，只适合于 i > 0 且 j > 0 的情况。

如果 obstacleGrid[i][j] == 1，则 dp[i][j] = 0。

如果 obstacleGrid[i][j] == 0，则 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

遍历整个网格之后，dp[m - 1][n - 1] 即为不同路径数。

##字符串算法

字符串匹配算法用于匹配模式在字符串中第一次出现的位置，其中字符串的长度是m，模式的长度是n，满足m>n。

暴力法的时间复杂度是O(mn)。

Rabin-Karp算法基于哈希实现，平均时间复杂度是O(m+n)。

Knuth-Morris-Pratt算法利用最大前缀信息，减少不必要的比较次数，时间复杂度是O(m+n)。