动态规划十大经典问题

动态规划十大经典问题数塔取数问题、矩阵取数问题、最大连续子段和、最长递增子序列、最长公共子序列、最长公共子串、最短编辑距离、背包问题、正整数分组、股票买卖问题。

dp-algorithm

1、数塔取数问题

// 数塔取数问题
public static int dataTowerAccess(int[][] dp) {
    int max = 0;
    for (int i = 1; i < dp.length; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + dp[i][j];
            }
            max = Math.max(dp[i][j], max);
        }
    }
    return max;
}

2、矩阵取数问题

// 矩阵取数问题
public static int matrixAccess(int[][] dp) {
    for (int i = 0; i < dp.length; i++) {
        for (int j = 0; j < dp[i].length; j++) {
            if (i == 0 && j > 0) {
                dp[i][j] = dp[i][j - 1] + dp[i][j];
            }
            if (j == 0 && i > 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j];
            }
            if (i > 0 && j > 0) {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + dp[i][j];
            }
        }
    }
    return dp[dp.length - 1][dp[0].length - 1];
}

3、最大连续子段和

// 最大连续子段和
public static int maxSubSum(int[] dp) {
    int max = dp[1];
    for (int i = 1; i < dp.length; i++) {
        dp[i] += Math.max(dp[i - 1], 0);
        max = Math.max(max, dp[i]);
    }
    return max;
}

4、最长递增子序列

// 最长递增子序列
public static int lis(int[] ints) {
    int[] dp = new int[ints.length];
    int max = 0;
    for (int i = 0; i < dp.length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (ints[j] < ints[i] && dp[j] > dp[i] - 1) {
                dp[i] = dp[j] + 1;
            }
            max = Math.max(dp[i], max);
        }
    }
    return max;
}

5、最长公共子序列

// 最长公共子序列
public static int lcs(char[] a, char[] b) {
    int high = a.length + 1;
    int width = b.length + 1;
    int[][] dp = new int[high][width];
    for (int i = 1; i < high; i++) {
        for (int j = 1; j < width; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return dp[high - 1][width - 1];
}

6、最长公共子串

// 最长公共子串
public static int lcs1(char[] a, char[] b) {
    int high = a.length + 1;
    int width = b.length + 1;
    int[][] dp = new int[high][width];
    int max = 0;
    for (int i = 1; i < high; i++) {
        for (int j = 1; j < width; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                max = Math.max(dp[i][j], max);
            }
        }
    }
    return max;
}

7、最短编辑距离

// 最短编辑距离
public static int med(char[] a, char[] b) {
    int high = a.length + 1;
    int width = b.length + 1;
    int[][] dp = new int[high][width];

    for (int i = 0; i < high; i++) {
        dp[i][0] = i;
    }

    for (int j = 0; j < width; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i < high; i++) {
        for (int j = 1; j < width; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
            }
        }
    }
    return dp[high - 1][width - 1];
}

8、背包问题

// 0-1 背包问题
public static int knapsack(int[] value, int[] weight, int capacity) {
    int high = value.length + 1;
    int width = capacity + 1;
    int[][] dp = new int[high][width];
    for (int i = 1; i < high; i++) {
        for (int j = 1; j < width; j++) {
            if (weight[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
            }
        }
    }
    return dp[high - 1][width - 1];
}

9、正整数分组

// 正整数分组（多重背包问题）
public static int pig(int[] ints) {
    int sum = 0;
    for (int item : ints) {
        sum += item;
    }
    int high = ints.length + 1;
    int width = sum / 2 + 1;
    int[][] dp = new int[high][width];
    for (int i = 1; i < high; i++) {
        for (int j = 1; j < width; j++) {
            if (ints[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - ints[i - 1]] + ints[i - 1]);
            }
        }
    }
    return dp[high - 1][width - 1];
}

10、股票买卖问题

// 股票买卖问题
public static int stockTrading(int[] price) {
    if (price.length == 0) {
        return 0;
    }
    int max = 0, minPrice = price[0];
    for (int i = 1; i < price.length; i++) {
        max = Math.max(max, price[i] - minPrice);
        minPrice = Math.min(minPrice, price[i]);
    }
    return max;
}