动态规划法的基本思想、时间复杂度

动态规划是一种解决多阶段决策过程最优化问题的方法。其基本思想是将原问题分解为若干个子问题，逐个求解这些子问题，并将子问题的解组合起来得到原问题的解。具体而言，动态规划法通常采用自底向上的方式，先求解小规模的子问题，再逐步推导出大规模的子问题，最终得到原问题的解。

动态规划法的时间复杂度取决于问题的规模和状态数目。通常情况下，动态规划法的时间复杂度是O(n^2)或O(n^3)级别的，其中n表示问题规模。在某些特殊情况下，动态规划法的时间复杂度可能会更低，例如最长公共子序列问题可以通过矩阵乘法优化到O(nlogn)级别。但是，对于一些NP完全问题，动态规划法的时间复杂度可能会非常高，甚至无法在多项式时间内求解。