学习笔记

动态规划

动态规划和递归或者分治没有根本上的区别（关键是看有无最优的子结构）

共性：找到重复子问题

差异性：最优子结构，中途可以淘汰次优解

动态规划关键点

1.最优子结构 opt[n] = best_of(opt[n-1],opt[n-2]...)

2.存储中间状态：opt[i]

3.递推公式 ：

Fib: opt[i] = opt[n-1]+opt[n-2]

二维路径：opt[i,j] = opt[i+1] [j] + opt[i] [j+1] (且判断a[i,j]是否空地)