NOTE.md

学习笔记

动态规划总结

1. 动态规划和递归或者分治的相同点：找到最简单的子结构，化繁为简
2. 动态规划和递归或者分治的差异性：动态规划可以在中途淘汰次优解，从而简化问题，近一步演变成递归形式

关于不同路径题目的状态转移方程

1. 没有石头的情况下：dp[i][j] = dp[i+1][j] + dp[i][j+1];
2. 在有石头的情况下，如果递推方程中某一个是石头，则石头所在位置处为0，即如果dp[i+1][j]是石头，则dp[i][j] = dp[i][j+1]; 如果dp[i][j+1]是石头，则dp[i][j] = dp[i+1][j];如果2个都是石头，则dp[i][j]=0

动态规划内功

1. 定义状态，定义子问题
2. 写出状态转移方程

字符串

1. 两个字符串之间的问题往往可以转换成一个而为平面上的问题
2. 高级字符串算法往往会和动态规划相结合，而且往往是二维或者更高维的