子序列

Dilworth 定理
    最长不上升子序列的最少划分数 == 最长上升子序列长度（LIS）

LIS
    状态表示
        dp[i] 表示以a[i] 为结尾的最长上升子序列长度
    状态转移方程
        dp[i] = max{ dp[j] + 1 };
            j∈[1, i - 1]
            a[i] > a[j]
    初值
        dp[1 ~ n] = 1
    目标
        max{ dp[i] }
            i∈[1 ~ n]

LCS
    状态表示
        dp[i][j] 表示前缀字串a[1 ~ i]和a[1 ~ j]的最长公共子序列
    状态转移方程
                        f[i - 1][j]
        dp[i][j] = max  f[i][j - 1]
                        f[i - 1][ j - 1] + 1 if( a[i] == a[j] )
    初值
        dp[1 ~ i][0] = dp[0][1 ~ i] = 0
    目标
        dp[n][m]

LCIS
    状态表示
        dp[i][j] 表示前缀字串a[1 ~ i]和a[1 ~ j]构成的以b[j]为结尾的LCIS的长度
    状态转移方程
        a[i] != b[j]
            dp[i][j] = dp[i - 1][j]
        a[i] == b[j]
            dp[i][j] = max{ dp[i - 1][k] + 1}
                1 <= k < j
                b[k] < b[j] == a[i]
    初值
        dp[i][0] = 0
    目标
        max{ dp[n][i] }
            i∈[1 ~ m]
    code
        for( int i = 1; i <= n; i ++ )
        {
            int maxx = 1;
            for( int j = 1; j <= n; j ++ )
            {
                if( a[i] != b[j] )
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = max( maxx, dp[i][j]);
                if( b[j] < a[i] )
                    maxx = max( maxx, dp[i - 1][j] + 1 ) ;
            }
         }