一维dp只代表数组是一维的,不代表只有一层for循环
最长不下降子序列LIS
建表
最长不下降子序列
dp[i]是指从1~i的最长不下降子序列长度
但是算dp[i],只知道dp[i-1]还不够
需要知道的是s[i]接在s[1]到s[i-1]后面所有的情况
在这些情况中取最大值,也就是需要知道dp[1]到dp[i-1]
这里就有一些问题:
如果按照之前的定义,dp[x]可能不包含x,这就没有办法作为之后的状态转移的依据;换言之,s[i]不是LIS中最大的那个值,就没法比较
所以添加一个限制:dp[i]必须包含x,s[i]是LIS中最大的那个值
填dp[0]
最长不下降子序列
0
填dp[i]
最长不下降子序列
全0
注意,这个dp[i][j]是一定要包含s[i]的,所以只有两种情况:
- 可以接在s[j]之后,dp[j]+1;
- 不可以接在s[j]之后。因为有dp[i]必须包含i的限制,所以只能是1,只包含一个s[i]的序列
dp[i][j] = s[i]>=s[j] ? dp[j]+1 : 1
dp[i] = max(dp[i][j]) 1<=j<=i-1
矫正
注意下标,i的有效值从1到n,对应数组元素的0到n-1