如何推导动态规划状态方程

要详细的推导动态规划方程方法，本人即将参加NOIP2009复赛！！

还有追加分！！

现在竞赛已经过了，好像只能明年派上用场了。 第一，确定最优化子问题 第二，定义问题解集合，确定维度的明确含义定义 第三，分析分治策略，并确定最优化子解归结为原问题的方法 - 转移方程出自这里 第四，初始化简单解 第五，确定推导顺序 第六，在结果集中寻找问题解。 动态规划的设计除了上述标准过程外，其他就需要因题目的不同而灵活运用，尤其是第一项和第二项尤为重要。

技巧就是：

看一下跟哪个，模型比较像（比如说背包问题）。

其实动态规划就是要看你这个状态是哪一些状态过来的，再在这些状态中选一个符合题意的即可。我们这个学校的信息组就是这样推DP的。

其实动态规划中还有一个是记忆化搜索。

今年没有考DP，真是令人意外啊，想想有一年3道DP啊！

实际上，动态规划只能说是个方法，而不是个算法。所以对不同的题目是不同的。

总得举个题目吧……状态转移方程（递推式）是根据题目的意思推导出来的，没有固定的流畅，只能靠积累和您的数学功底以及智商。