Question

动态规划求解活动选择

Answer 1

动态规划求解活动选择
什么是动态规划
动态规划是一种常用的优化算法，它是解决一类最优化问题的有效方法。动态规划算法的特点是将原问题分解成多个子问题，分别求解子问题，再依次合并子问题的解，从而得到原问题的最优解。

活动选择问题
活动选择问题是指在一组活动中选出最合适的活动集合，使得该集合所包含的各项活动互不冲突，并且这个集合中的活动数最大。这个问题可以用动态规划算法求解。

活动选择问题的动态规划解法
首先我们需要将问题分解成多个子问题。假设有n个活动，编号为1,2,...,n。对于这n个活动，我们需要按照它们的结束时间从早到晚排序，以便于接下来的动态规划算法。令f[i]表示前i个活动中所选出的最大活动数量。那么状态转移方程为:

f[i]=max{f[j]}+1，其中j