Java算法系列第十七篇：动态规划详解

动态规划是一种强大的算法，通过将问题分解为子问题，并保存子问题的解，能够有效解决许多最优化问题。本文介绍了动态规划的基本概念、应用场景及其实现方法，希望能够帮助你更好地理解和应用动态规划解决实际问题。你的支持是我持续创作的动力！下期我们将详细讲解图算法中的最短路径算法，敬请期待！这篇文章详细介绍了动态规划的基本概念、应用场景及其实现方法。如果你有任何问题或建议，欢迎在评论区留言！

阿里渣渣java研发组-群主

717人浏览 · 2024-06-03 20:15:16

阿里渣渣java研发组-群主 · 2024-06-03 20:15:16 发布

Java算法系列第十七篇：动态规划详解

动态规划（Dynamic Programming，DP）是一种解决最优化问题的算法，通过将问题分解为子问题，逐步解决子问题来获得原问题的解。动态规划广泛应用于各种领域，如图论、字符串处理、序列比对等。本文将详细介绍动态规划的基本概念、应用场景及其实现方法。

一、动态规划的基本概念

动态规划的基本思想是将问题分解为相互重叠的子问题，通过保存子问题的解来避免重复计算。动态规划通常包括以下几个步骤：

定义子问题：将原问题分解为若干个子问题。
确定状态转移方程：找到子问题之间的递推关系。
边界条件：确定初始状态的值。
递推计算：根据状态转移方程和边界条件逐步计算子问题的解。

二、动态规划的应用场景

动态规划适用于以下几种场景：

最短路径问题：如Bellman-Ford算法。
最长公共子序列：求解两个序列的最长公共子序列。
背包问题：求解0/1背包问题和完全背包问题。
字符串编辑距离：求解两个字符串之间的编辑距离。

三、动态规划的实现

下面是几个常见的动态规划算法实现示例：

1. 斐波那契数列

斐波那契数列是一个经典的动态规划问题，通过递推计算斐波那契数。

public class Fibonacci {

    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci(" + n + ") = " + fib(n));
    }
}

2. 最长公共子序列

最长公共子序列问题是求解两个序列的最长公共子序列。

public class LongestCommonSubsequence {

    public static int lcs(String s1, String s2) {
        int m = s1.length();
        int k = s2.length();

        int[][] dp = new int[m + 1][k + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= k; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][k];
    }

    public static void main(String[] args) {
        String s1 = "ABCBDAB";
        String s2 = "BDCABA";
        System.out.println("最长公共子序列长度：" + lcs(s1, s2));
    }
}

3. 0/1背包问题

0/1背包问题是经典的动态规划问题，通过递推计算背包的最大价值。

public class Knapsack {

    public static int knapsack(int W, int[] weights, int[] values, int n) {
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int W = 5;
        int n = weights.length;

        System.out.println("0/1背包最大价值：" + knapsack(W, weights, values, n));
    }
}

4. 编辑距离

编辑距离问题是求解两个字符串之间的最小编辑距离。

public class EditDistance {

    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        System.out.println("编辑距离：" + minDistance(word1, word2));
    }
}