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

2024-12-16 18:45:16

推荐回答（4个）

回答1：

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

回答2：

技巧就是：看一下跟哪个，模型比较像（比如说背包问题）。其实动态规划就是要看你这个状态是哪一些状态过来的，再在这些状态中选一个符合题意的即可。我们这个学校的信息组就是这样推DP的。其实动态规划中还有一个是记忆化搜索。今年没有考DP，真是令人意外啊，想想有一年3道DP啊！

回答3：

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

回答4：

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