本文共 719 字，大约阅读时间需要 2 分钟。

动态规划算法：

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。

例子：最长公共子序列问题

String str1="androdid"; String str2="random";

最长公共子序列：ando,只考虑顺序不考虑中间是否间隔，不同于公共字符串and。

该问题的递归式子可以写成：

注意以下代码求最长公共子序列问题，矩阵第一行和第一列初始化，其他由递归公式生成。

最长公共子序列问题Java实现：

package com.algorithm.lcs;/** * 动态规划--最长公共子序列 */public class LCS {    public static void main(String[] args) {        String str1="androdid";        String str2="random";        findLCS(str1,str2);    }    private static void findLCS(String str1, String str2) {        int m=str1.length();        int n=str2.length();        char[] chars1=str1.toCharArray();        char[] chars2=str2.toCharArray();        int[][] dp=new int[m][n];        for(int i=0;i