最长回升子序列
给定一个无序的整数数组，找到其中最长回升子序列的长度。例如对于[10,9,2,5,3,7,101,18]返回4。
思考第i位数字nums[i]是否能够继承之前的状态，须要晓得之前状态子序列的长度n与最右值m。如果nums[i]大于m，状态i的长度为n+1，最右值为nums[i]。
上述的动静布局过程能够用一维数组记录中间状态，对于status[i]记录了以nums[i]为子序列最初一个元素的子序列长度。status[i]的计算须要遍历之前的所有状态，取最大长度。
def solution(nums): if not nums: return 0 status = [1]*len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: status[i] = max(status[i], status[j]+1) return max(status)最长公共子序列
给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。例如对于text1 = "abcde"，text2 = "ace" 返回3。
思考对于中间状态(i, j)，text1[i]与text2[j]的退出是否对已有状态产生了影响。
- text1[i]与text2[j]的退出对已有状态无影响，状态(i, j) = 状态(i-1, j-1) 。
- text1[i]与text2[j-1]匹配，状态(i, j) = 状态(i, j-1)。
- text2[j]与text1[i-1]匹配，状态(i, j) = 状态(i-1, j)。
- text1[i] == text2[j]，text[i]与text[j]匹配，状态(i, j) = 状态(i-1, j-1) + 1。
上述的动静布局过程能够用二维数组记录中间状态，对于status[i][j]记录了text[:i]与text[:j]的最长公共子序列的长度。status[i][j]的计算依赖于status[i-1][j]，status[i][j-1]，status[i-1][j-1]。
def solution(text1, text2): n, m = len(text1), len(text2) status = [[0]*(m+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, m+1): status[i][j] = max(status[i-1][j], status[i][j-1]) if text1[i-1] == text2[j-1]: status[i][j] = max(status[i][j], 1 + status[i-1][j-1]) return status[n][m]对于状况1，曾经蕴含在status[i-1][j]或status[i][j-1]中。