简单一维动态规划

一维动态规划是一种常见的算法技术，用于解决一维状态空间的最优化问题。它的核心思想是通过存储中间计算结果，以便在后续计算中重复使用，从而避免重复计算，提高算法效率。

下面是一个简单的一维动态规划的例子，以求解最长递增子序列（Longest Increasing Subsequence，简称LIS）为例：

问题描述：给定一个整数序列，找到其中最长的递增子序列的长度。

动态规划解法：

1. 定义状态：dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。

2. 初始化：将所有 dp[i] 初始化为 1，因为一个元素本身就是一个递增子序列。

3. 状态转移方程：对于每个位置 i，遍历前面所有位置 j (0 <= j < i)，如果 nums[i] > nums[j]，则说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面，形成一个更长的递增子序列，即 dp[i] = max(dp[i], dp[j] + 1)。

4. 最终结果：遍历整个 dp 数组，找到最大的 dp[i] 值，即为最长递增子序列的长度。

下面是一个使用动态规划解决最长递增子序列问题的 Python 代码示例：

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n  # 初始化 dp 数组为 1

    for i in range(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]
print(longest_increasing_subsequence(nums))  # 输出：4

在上面的代码中，我们使用了两层循环，时间复杂度为 O(n^2)，其中 n 是输入序列的长度。通过动态规划的思想，我们避免了重复计算，将问题的规模从指数级别降低到了多项式级别，提高了算法的效率。