动态规划系列(1): 线性DP

从斐波那契数列说起

可能你从来没有接触过动态规划,只是隐约听别人提起过DP是种特别厉害的算法;又或许你已经看过动态规划的相关定义和教程,能够做一些像LCS、数字三角形之类的简单DP题目。

但无论你对DP了解如何,阅读本文都会使你对动态规划有更为清晰的认识。不同于你可能看过的很多资料,本文将会以一种更为崭新的视角,从更为本质而数学化的角度出发,尽力发掘出隐藏在所谓的“状态转移方程”、“最优子结构”等重重迷雾下动态规划的真实一面。

阅读更多