动态规划问题

讲到算法问题,通常都是以排序作为开始。 在面对实际问题是,大多是结合了动态规划(Dynamic Programming)的解法。在实际运用中的排序,最短路径,资源最优分配等问题上,都采用了使用动态规划的解法。

因为动态规划将问题分解到单阶的子问题,并且对单阶子问题的解做了存储,因此能在运算效率上有所保证,并且能比较有效避免指数级别增长的性能问题。

比较基础和经典的动态规划算法有以下几个:

另外在这里有一些关于运用动态规划解决一些比较实用问题的文章和讨论。

一些公司喜欢面试算法题,在一些比较难的问题上,尤其是需要考虑到实现的算法效率问题时,动态规划的思路是比较常用的一个手法。事实上zack有点怀疑一些题目的目的就是为了检验下是否对动态规划问题有概念,毕竟对于大部分算法课来说,讲到《算法导论》中关于动态规划的那一章时,所剩的时间已经不多了,而且可能根本也不会详细讲解。