动态规划(Dynamic Programming)是一种以时间换空间，将指数复杂度的搜索转化为 多项式复杂度解的技术。其中 Programming 指一种表格方法，而不是编程。
此表部分总结，收集于《算法导论》以及个人经验。
对于不同整数长度的钢条，我们给出不同的价格。现在可以任意对一条钢条切割， 求可以获得的最大价值。
很容易想到的，由于钢条长度为整数，对一根长度为 n 的钢条我们只能在 n - 1 个 位置上切割。于是可以使用这样的代码（Lua）
-- Assuming that the values are stored in table value
local cutRod;
cutRod = function(l)
local v = 0;
for i = 1,l
do
v = math.max(v,cutRod(l - i) + value[i]);
end
return v;
end
这段代码肯定工作，但是让我们分析一下它做了什么
简记 cutRod(l) 为 T(l)
对于 T(4)，它需要计算 T(1),T(2),T(3)
T(2) 计算 T(1);T(3) 计算 T(2) T(1)
最终我们会发现，对于小的 l，T(l) 被多次计算，事实上 cutRod() 一共被调用了 8 次 才得出结果，对于更大的 l 这个数字会更加恐怖。
一种自然的联想是，我们可以把 T(l) 的返回值保存起来，这样可以避免重复计算了
-- Assuming that the values are stored in table value
local cutRod,mem = nil,{}; -- A better way is to create a factory
cutRod = function(l)
if mem[l]
then
return mem[l];
end
local v = 0;
for i = 1,l
do
v = math.max(v,cutRod(l - i) + value[i]);
end
mem[l] = v;
return v;
end
这就可以了。
函数调用是有消耗的。而如果我们仔细观察开始的暴力解，我们可以写出一个式子: $$ cutRod(l) = \begin{cases} value[l] & l = 1 \\ max \{ p \vert 1 \leq p \leq l \} & \text{otherwise} \end{cases} $$ （这个式子通常被叫做递推式）
观察到，对于 cutRod(l) 的计算事实上只依赖 cutRod(0) ... cutRod(l)。如果我们
从 cutRod(0) 逐步推后计算，我们有可能一定能消除掉递归。
local dp = {[0] = 0};
for l = 1,length
do
local v = 0;
for p = 1,l
do
v = math.max(v,value[p] + dp[l - p]);
end
dp[l] = v;
end
恭喜你，时间复杂度已经变成了 $\Theta(n^2)$
我们从一个暴力算法开始，利用记忆化将它优化到多项式复杂度，再通过展开递归式 来优化常量因子。这次事件中我们可以得到一些关于动态规划的有关事项：
滚动数组 优化空间复杂度。有的时候递归式向前依赖的
子问题是有限的（例如背包问题），此时滚动数组是可用的