算法学习——动态规划

关于动态规划的经典算法，如多段图最短路径问题、TSP问题、最长公共子序列问题等。

动态规划

经典算法

数塔问题

public static int Tower(int[][] d) {
    int n = d.length;
    int[][] maxAdd = new int[n][n];
    int[][] path = new int[n][n];
    int i, j;
    for (j = 0; j < n; j++) {
        maxAdd[n - 1][j] = d[n - 1][j];
    }
    for (i = n - 2; i >= 0; i--) {
        for (j = 0; j <= i; j++) {
            if (maxAdd[i + 1][j] > maxAdd[i + 1][j + 1]) {
                maxAdd[i][j] = d[i][j] + maxAdd[i + 1][j];
                path[i][j] = j;
            } else {
                maxAdd[i][j] = d[i][j] + maxAdd[i + 1][j + 1];
                path[i][j] = j + 1;
            }
        }
    }
    System.out.println("路径：" + d[0][0]);
    j = path[0][0];
    for (i = 1; i < n; i++) {
        System.out.println("-->" + d[i][j]);
        j = path[i][j];
    }
    System.out.println(Arrays.deepToString(maxAdd));
    return maxAdd[0][0];
}

多段图最短路径问题

public static int BackPath(Graph graph) {
    int n = graph.getVnum();
    int i, j, temp;
    int[] cost = new int[n];
    int[] path = new int[n];
    for (i = 1; i < n; i++) {// 初始化路径为∞
        cost[i] = MAX;
        path[i] = -1;
    }
    cost[0] = 0;// 0为源点
    path[0] = -1;
    for (j = 1; j < n; j++) {// 填表
        for (i = j - 1; i >= 0; i--) {// 考察所有入边
            if (graph.getMatrix()[i][j] >= 0)// 如果边存在
                if (graph.getMatrix()[i][j] + cost[i] < cost[j]) {
                    cost[j] = graph.getMatrix()[i][j] + cost[i];
                    path[j] = i;
                }
        }
    }
    System.out.println("-----" + (n - 1));// 输出终点
    i = n - 1;
    while (path[i] >= 0) {// 依次输出path[i]
        System.out.println("-----" + path[i]);
        i = path[i];// 路径上顶点i的前一个顶点
    }
    System.out.println(Arrays.toString(cost));
    return cost[n - 1];
}

多源点最短路径问题（Floyd算法）

public static int[][] FloydAlgorithm(Graph graph) {
    int i, j, k;
    int n = graph.getVnum();
    int[][] dist = new int[n][n];
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            dist[i][j] = graph.getMatrix()[i][j];
        }
    }
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (i != j && i != k && k != j)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    return dist;
}

TSP问题（待解决）

最长递增子序列问题

public static int IncreaseOrder(int[] a) {
    int i, j, k, index;
    int n = a.length;
    int[] L = new int[n];
    int[][] x = new int[n][n];
    for (i = 0; i < n; i++) {// 初始化，最长递增子序列长度为1
        L[i] = 1;
        x[i][0] = a[i];
    }

    System.out.println("初始化完成");
    for (int[] item : x) {
        System.out.println(Arrays.toString(item));
    }

    for (i = 1; i < n; i++) {
        int max = 1;
        for (j = i - 1; j >= 0; j--) {
            if ((a[j] < a[i]) && (max < L[j] + 1)) {
                max = L[j] + 1;
                L[i] = max;
                for (k = 0; k < max - 1; k++) {
                    x[i][k] = x[j][k];
                }
                x[i][max - 1] = a[i];
            }
        }
    }
    for (index = 0, i = 1; i < n; i++) {// 求所有递增子序列的最大长度
        if (L[index] < L[i])
            index = i;
    }
    System.out.println("最长子序列：");
    for (i = 0; i < L[index]; i++) {// 输出最长递增子序列
        System.out.println(x[index][i]);
    }

    for (int[] item : x) {
        System.out.println(Arrays.toString(item));
    }

    return L[index];// 返回最长递增子序列的长度
}

最长公共子序列问题

private static int CommonOrder(char[] x, char[] y) {
    int i, j, k;
    int n = y.length, m = x.length;
    char[] Z = new char[Math.max(n, m)];// 存储最长公共子序列
    int[][] DP = new int[m + 1][n + 1];// 长度矩阵
    int[][] S = new int[m + 1][n + 1];// 状态矩阵
    for (j = 0; j <= n; j++)// 初始化第0行
        DP[0][j] = 0;
    for (i = 0; i <= m; i++)// 初始化第0列
        DP[i][0] = 0;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            if (x[i - 1] == y[j - 1]) {// 情况①：两字符相同，此处i和j减一是因为矩阵中前面要留出一个空字符的位置，对应到原字符串中就需要减一
                DP[i][j] = DP[i - 1][j - 1] + 1;// 左上方的数字+1填入
                S[i][j] = 1;
            } else if (DP[i][j - 1] >= DP[i - 1][j]) {// 情况②：两字符不同，且左侧的数>=上方的数
                DP[i][j] = DP[i][j - 1];// 填入左侧数字
                S[i][j] = 2;
            } else {// 情况③：两数字不同，且左侧的数<上方的数
                DP[i][j] = DP[i - 1][j];// 填入上方数字
                S[i][j] = 3;
            }
    i = m;
    j = n;
    k = DP[m][n];// 从长度矩阵的最后一个元素开始回溯
    while (i > 0 && j > 0) {
        if (S[i][j] == 1) {// 情况①：往左上方回溯，同时记录当前字符
            Z[k] = x[i - 1];
            k--;
            i--;
            j--;
        } else if (S[i][j] == 2) {// 情况②：往左侧回溯
            j--;
        } else {// 情况③：往上方回溯
            i--;
        }
    }

    for (k = 1; k <= DP[m][n]; k++) {
        System.out.println(Z[k]);
    }

    return DP[m][n];
}

0/1背包问题

public static int KnapSack(int[] w, int[] v, int C) {// w:物品重量,v:物品价值,C:背包容量
    int i, j;
    int n = w.length;
    int[] x = new int[n];// 存放物品装入情况
    int[][] V = new int[n + 1][C + 1];// 迭代数组,含义:任取物品[0,i]放入容量为j的背包中
    for (i = 0; i <= n; i++)// 初始化第0列
        V[i][0] = 0;
    for (j = 0; j <= C; j++)// 初始化第0行
        V[0][j] = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= C; j++)
            if (j < w[i - 1])// 当前迭代的容量如果小于物品重量
                V[i][j] = V[i - 1][j];// 则不放入物品，总价值与它上方的数值相同
    else// 否则，取“上方数值”和“不放物品i时的最大价值+物品i的价值”较大者
        V[i][j] = Math.max(V[i - 1][j], V[i - 1][j - w[i - 1]] + v[i - 1]);
    for (j = C, i = n; i > 0; i--) {
        if (V[i][j] > V[i - 1][j]) {
            x[i - 1] = 1;
            j = j - w[i - 1];
        } else
            x[i - 1] = 0;
    }

    System.out.println(Arrays.toString(x));

    return V[n][C];// 返回最大价值
}

最优二叉搜索树（待解决）

近似串匹配问题（待理解）

public static int ASM(char[] P, char[] T) {
    int i, j;
    int m = P.length, n = T.length;
    int[][] D = new int[m + 1][n + 1];
    for (j = 1; j <= n; j++)
        D[0][j] = j;
    for (i = 0; i <= m; i++)
        D[i][0] = i;
    for (j = 1; j <= n; j++) {
        for (i = 1; i <= m; i++) {
            if (P[i - 1] == T[j - 1])
                D[i][j] = Math.min(Math.min(D[i - 1][j - 1], D[i - 1][j] + 1), D[i][j - 1] + 1);
            else
                D[i][j] = Math.min(Math.min(D[i - 1][j - 1] + 1, D[i - 1][j] + 1), D[i][j - 1] + 1);
        }
    }

    return D[m][n];
}

练习

力扣.1143. 最长公共子序列

以序列X={a,b,c,b,d,b}和Y={a,c,b,b,a,b,d,b,b}为例

长度矩阵为：

	0	a	c	b	b	a	b	d	b	b
0	0	0	0	0	0	0	0	0	0	0
a	0
b	0
c	0
b	0
d	0
b	0

• 表格的第一行、第一列全部初始化为0，表示空字符串与任何字符串的最长公共子序列长度均为0
• 从第一个空格开始遍历表格
  • 若所在行和列的字符不相同，则在它上方和左侧的两个数字中选取较大的一个填入（DP[i][j] = max{DP[i-1][j], DP[i][j-1]}）
  • 若所在行和列的字符相同，则将它左上方的数字+1填入（DP[i][j] = DP[i-1][j-1] + 1）
• 在处理上述矩阵的同时，可定义另一个格式相同的矩阵用来记录状态，成为状态矩阵
  • 情况①，两字符相同，则填入1
  • 情况②，两字符不同，且长度矩阵中左侧数字>=上方数字，则填入2
  • 情况③，两字符不同，且长度矩阵中左侧数字<上方数字，则填入3
• 回溯时，从状态矩阵的最右下角元素开始
  • 遇到1，向左上方回溯
  • 遇到2，向左侧回溯
  • 遇到3，向上方回溯
• 回溯至最左上角元素后，经过的路线中所有1所在位置对应的字符组成的字符串即为最长公共子序列