Python 动态规划求最长递增子序列长度

给定一个整数序列，找到其中最长严格递增子序列的长度。

动态规划表：

| | 2 | 5 | 3 | 4 | 7 | 6 | | - | - | - | - | - | - | - | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | 2 | 1 | 2 | 1 | 2 | 3 | 2 | | 3 | 1 | 2 | 2 | 2 | 3 | 2 | | 4 | 1 | 2 | 2 | 3 | 4 | 3 | | 5 | 1 | 2 | 2 | 3 | 4 | 3 | | 6 | 1 | 2 | 2 | 3 | 4 | 4 |

最长递增子序列的长度为 4。

代码：

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    print('动态规划表：')
    for i in range(n):
        print(dp[i], end=' ')
    print('\n')
    return max(dp)

nums = [2, 5, 3, 4, 7, 6]
print('最长递增子序列的长度为：', longest_increasing_subsequence(nums))

解释：

dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
初始化 dp 为全 1，因为每个元素自身都是一个长度为 1 的递增子序列。
遍历 nums，对于每个 i，遍历 0 到 i-1，如果 nums[j] < nums[i]，则 dp[i] 可以取 dp[j] + 1，表示在 nums[j] 结尾的最长递增子序列后面加上 nums[i]，得到一个新的更长的递增子序列。
最后，max(dp) 就是最长递增子序列的长度。

总结：

使用动态规划算法可以有效地求解最长递增子序列问题。通过构建一个动态规划表，我们可以记录每个位置结尾的最长递增子序列长度，并最终求出最长递增子序列的长度。