bittib

public String lcs(String a, String b){
    int m = a.length(), n = b.length();
    int[][] f = new int[m+1][n+1];
    for (int i=0; i<=n; i++)
        f[0][i] = 0;
    for (int i=0; i<=m; i++)
        f[i][0] = 0;
    for (int i=1; i<=m; i++){
        for (int j=1; j<=n; j++){
            if (a.charAt(i-1) == b.charAt(j-1))

bittib

// DP version, Time Complexity : O(n^2)
public int lis(int[] A){
    if (A == null || A.length == 0) return 0;
    int n = A.length;
    int[] f = new int[n];
    for (int i=0; i<n; i++){
        f[i] = 1;
        for (int j=0; j<i; j++){
            if (A[j] <= A[i] && f[j] + 1 > f[i])
                f[i] = f[j] + 1;

bittib

/**
 * 最简单的01背包
 * N个物品，装入重量大小为M的包，每个物品重w[i]，价值p[i], 求包内最大价值
 * 输入规模 ：1<=N<=3402, 1<=M<=12880
 * 
 * 设f[i][j]是前i个物品装入重量大小为j的包的最大值,
 * f[i][j] = max{f[i-1][j], f[i-1][j-w[i]] + p[i]}
 * 最终结果是f[n-1][m]
 * 
 * 时间复杂度为O(N*M),空间复杂度为O(N*M),空间复杂度可以优化到O(N)

bittib

import java.io.*;
public class Main{

    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static int N = 8; 
    static int cnt = 0;

    public static void main(String[] args){
        int[] array = new int[N];
        cnt = 0;