字符串输入的一般解决思路
- 选择suffix作为子问题
- 选择prefix作为子问题
- 使用子集substring
- 有时候单个的选择已经不够了，比如背包问题，不仅需要知道要选择哪个物件，来得到价值，同时也需要知道还剩多少容量，也就是需要"记住"更多的子问题，或者说子条件来处理问题
编辑距离
给定两个字串x和y,将x变成y所需要改变的字符的个数是多少？期间可以的操作是:
- 插入字符c 耗时O(1)
- 删除字符c 耗时O(1)
- 将c更新为c' 如果C和C'是相同的，耗时O(0)，其它不考虑
字串可以是非连续的。它等效于找两个字符串的最大公共字串，比如 HIEROGLYPHOLOGY 和 MICHAELANGELO 最大公共字串为 HELLO
动态规划思路
- 子问题：X的子串X[i:]和Y的子串Y[j:]
数量为:
)
- 猜测：只有3中可能的方式，要么把X[i]替换成Y[i],要么删掉X[i],要么把Y[i]插入X
-
循环：
DP(i,j)=min(cost of replace X[i] to Y[j]+ DP(i+1,j+1)，cost of delete X[i]+DP(i+1,j)，cost of insert Y[j]+DP(i,j+1) )
子问题的耗时:O(1)
-
拓扑排序：三个方向由右下角向左下角开始执行
for i in 0,...,|x|:
for j in 0,...,|y|:
复制代码原始的问题:DP(0,0)，总的时间为:O(1)*O(|x||y|)
矩阵相乘在哪个部分加括号运算才能使得运算最优
假设有如下形式的矩阵做乘法
扩展到假设有n个矩阵相乘
思路
最终总会是两个矩阵相乘，那这两个矩阵是怎么计算得到的？假设有一次区分，那么它是（
）.（
）这种样子,左边括号中也会继续按照这种方式划分，同理右边也需要，当左右两边都需要类似计算的时候，这种时候通常就是取substring
