动态规划法的基本思想是将待求解问题分解成什么问题

动态规划法的基本思想是将待求解问题分解成子问题，通过维护一个状态数组，逐步求解子问题并将结果保存，最终得到原问题的解。动态规划法广泛应用于计算机科学、数学、物理学等领域，是一种常用的优化问题求解方法。下面从多个角度分析动态规划法的基本思想。

一、分治思想

动态规划法的基本思想与分治思想有些类似。分治思想是将原问题分成若干个子问题，递归求解这些子问题，最后组合子问题的结果得到原问题的解。动态规划则是将原问题转化为若干个子问题，递归求解这些子问题，将子问题的解存储在状态数组中，最后利用子问题的解得到原问题的解。可以看出，动态规划法在分治思想的基础上增加了一个存储子问题解的步骤，能够更高效地解决一些问题。

二、最优子结构性质

动态规划法求解问题的前提条件是问题具有最优子结构性质。所谓最优子结构性质是指问题的最优解包含其子问题的最优解。也就是说，如果能够求出子问题的最优解，并将其存储在状态数组中，那么在求解原问题时就可以利用子问题的最优解得到更优的解。例如，最短路径问题，每个子问题的最优解都可以通过相邻两个顶点的最短路径得到。因此，在求解原问题时只需要选择经过的所有顶点的最短路径即可。

三、无后效性

动态规划法还具有无后效性。所谓无后效性是指一个阶段的状态一旦确定，就不受之后阶段的状态影响。也就是说，求解子问题时不需要考虑子问题的子问题。例如，最长公共子序列问题，当前子问题的最长公共子序列不会受到以后子问题的影响。

四、重叠子问题

动态规划法还利用了问题的重叠子问题。重叠子问题指子问题之间存在公共的子问题。在动态规划求解过程中，很多子问题会被重复求解，如果每次都对相同的子问题进行递归求解，显然会浪费很多时间。因此，动态规划法将子问题的解存储在状态数组中，并在求解子问题前先检查状态数组中是否已有解，如果有则直接使用，避免了重复计算，提高了求解效率。

综上所述，动态规划法的基本思想是将待求解问题分解成子问题，通过维护一个状态数组，逐步求解子问题并将结果保存，最终得到原问题的解。动态规划法要求问题具有最优子结构性质、无后效性和重叠子问题。动态规划法广泛应用于计算机科学、数学、物理学等领域，是一种常用的优化问题求解方法。