动态规划算法简单介绍

server/2024/9/24 2:07:16/

动态规划（Dynamic Programming，DP）是一种用于解决具有重叠子问题和最优子结构性质的问题的算法技术。它通过将复杂问题分解为更简单的子问题，并利用子问题的解来构建原问题的解，从而避免重复计算，提高效率。

动态规划的基本思想

动态规划的核心思想是通过分治和记忆化（即存储子问题的解），避免重复计算，从而提高算法的效率。动态规划一般包括以下几个步骤：

定义子问题：将原问题分解为一系列子问题。
递推关系：找到子问题之间的关系，建立递推公式。
边界条件：确定子问题的初始条件（即边界条件）。
计算顺序：确定计算子问题的顺序（通常是自底向上，或者递归加记忆化）。

动态规划的实现方式

动态规划有两种实现方式：自顶向下的递归加记忆化（Memoization）和自底向上的迭代（Tabulation）。

示例问题

以下是一些经典的动态规划问题及其解决方案：

1. 斐波那契数列

斐波那契数列是一个简单的动态规划问题，目标是计算第 𝑛n 个斐波那契数。

递归加记忆化

import java.util.HashMap;
import java.util.Map;public class FibonacciMemoization {private static Map<Integer, Integer> memo = new HashMap<>();public static void main(String[] args) {int n = 10;System.out.println(fibonacci(n)); // 输出第10个斐波那契数}public static int fibonacci(int n) {if (n <= 1) {return n;}if (memo.containsKey(n)) {return memo.get(n);}int result = fibonacci(n - 1) + fibonacci(n - 2);memo.put(n, result);return result;}
}

自底向上

public class FibonacciTabulation {public static void main(String[] args) {int n = 10;System.out.println(fibonacci(n)); // 输出第10个斐波那契数}public static int fibonacci(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];}
}

2. 最长公共子序列（LCS）

最长公共子序列问题是另一个经典的动态规划问题。给定两个字符串，找到它们的最长公共子序列的长度。

动态规划实现

public class LongestCommonSubsequence {public static void main(String[] args) {String text1 = "abcde";String text2 = "ace";System.out.println(longestCommonSubsequence(text1, text2)); // 输出 3}public static int longestCommonSubsequence(String text1, String text2) {int m = text1.length();int n = text2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1.charAt(i - 1) == text2.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][n];}
}