动态规划是一种解决多阶段决策问题的优化方法，它通过将问题分解为子问题并记录其结果，以避免重复计算，从而在整体上获得更好的性能。动态规划常常用于解决具有最优子结构性质的问题，即问题的最优解可以通过其子问题的最优解来构造。
动态规划的核心思想是将问题分解为一系列子问题，解决这些子问题，并存储其结果，以便在需要时直接获取，避免重复计算。
以下是一个经典的动态规划问题和应用的例子：最长递增子序列（Longest Increasing Subsequence，LIS）。
问题描述：
给定一个未排序的整数数组，找到最长递增子序列的长度。
动态规划解法：
def length_of_lis(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n # 初始化dp数组，每个元素表示以当前位置为结束的最长递增子序列长度
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
result = length_of_lis(nums)
print(result) # 输出：4，因为最长递增子序列是 [2, 3, 7, 101]
在这个例子中，动态规划的状态转移方程是 dp[i] = max(dp[i], dp[j] + 1)，表示考虑以第 i 个元素结尾的最长递增子序列，如果前面的某个元素 j 比 i 小，那么就可以将以 j 结尾的最长递增子序列长度加一作为以 i 结尾的递增子序列的候选值。
这个算法的时间复杂度是 O(n^2)，但也有更优化的 O(n log n) 的算法。这个问题展示了动态规划在解决实际问题中的强大能力，通过记录子问题的最优解，避免了重复计算，提高了算法的效率。
