（1）简述动态规划和贪心算法的基本思想。

动态规划和贪心算法都是解决最优化问题的算法。

动态规划的基本思想是将原问题分解成若干个子问题，先求解子问题，再逐步递推回原问题，从而得到最终的解。动态规划算法一般用于求解具有最优子结构的问题，即原问题的最优解可以由子问题的最优解推导出来。动态规划算法的核心是设计状态和状态转移方程，通过自底向上的递推求解子问题的最优解，最终得到原问题的最优解。

贪心算法的基本思想是在每一步选择中都采取当前状态下最优的选择，从而达到全局最优的结果。贪心算法一般用于求解具有贪心选择性质的问题，即每一步的最优选择都会对后续的选择产生影响。贪心算法不需要对子问题进行求解，因此通常比动态规划算法更加高效。但是，贪心算法不能保证得到全局最优解，有时会得到局部最优解。