动态规划算法python

动态规划（Dynamic Programming）是一种算法设计和优化的方法，用于解决具有重叠子问题性质的问题。在使用动态规划算法时，我们将复杂问题分解为一系列相互关联的子问题，并利用已经求解过的子问题的解来求解更大规模的问题。

下面是一个使用动态规划算法解决最长递增子序列（Longest Increasing Subsequence）问题的示例代码：

def lis(nums):
    n = len(nums)
    dp = [1] * n

    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, 22, 9, 33, 21, 50, 41, 60]
print(lis(nums))  # 输出: 5

这段代码通过使用一个辅助数组 `dp` 来记录以每个元素为结尾的递增子序列的最大长度。在每次迭代中，我们比较当前元素与之前元素的大小关系，若当前元素大于之前元素，则更新最大长度。

动态规划算法在许多问题中都有应用，如最短路径问题、背包问题等。通过将问题分解为子问题，并利用已经求解过的子问题的解，动态规划算法能够高效地解决复杂问题。