动态规划也是一种分治思想,但与分治算法不同的是,分治算法是把原问题分解为若干子问题,自顶向下求解各子问题,合并子问题的解,从而得到原问题的解。动态规划也是把原问题分解为若干子问题,然后自底向上,先求解最小的子问题,把结果存储在表格中,再求解大的子问题时,直接从表格中查询小的子问题的解,避免重复计算,从而提高算法效率。