学习笔记
[TOC]
动态规划 和 递归或者分治 没有根本上的区别(关键看有无最优的子结构)
共性:找到重复子问题
差异性:最优子结构、中途可以淘汰次优解
-
最优子结构 opt[n] = best_of(opt[n-1], opt[n-2], ...)
-
储存中间状态:opt[i]
-
递推公式(美其名曰:状态转移方程或者 DP 方程)
Fib: opt[i] = opt[n-1] + opt[n-2] 二维路径:opt[i,j] = opt[i+1][j] + opt[i][j+1] (且判断a[i,j]是否空地)
最长公共子序列 DP 方程
if S1[-1] != S2[-1]: LCS[s1, s2] = Max(LCS[s1-1, s2], LCS[s1, s2-1])
if S1[-1] == S2[-1]: LCS[s1, s2] = LCS[s1-1, s2-1] + 1