1、定义

求解具有最优性质问题的方法。例如最短路径问题等。

2、概念

2.1、阶段

将待求解问题拆分而成的若干个互相联系的过程。描述阶段的变量称为阶段变量。

2.2、状态

表示每个阶段起点或其上个阶段终点的客观条件。描述状态的变量称为状态变量。

2.3、决策

一个阶段的状态给定后，从该状态演变到下一阶段某个状态的动作。描述决策的变量称为决策变量。

2.4、策略

由每个阶段的决策组成的序列。所有可能的策略称为策略集合。策略集合中达到最优效果的策略称为最优策略。

3、适合动态规划解决的问题

3.1、原问题的最优解所包括的子问题的解也是最优的

3.2、任意阶段的决策无法影响其之前的状态

3.3、原问题拆分的子问题之间互相联系

4、动态规划的求解方法

4.1、分阶段

4.2、找状态

4.3、做决策

4.4、状态转移

4.5、找最优策略

4.6、找终止条件

5、例题

求解指定两个字符串的最大公共子字符串。例如下图，字符串str1="gfqnabxp"，字符串str2="xpqna"，它们的最大公共子字符串是"qna"。

image.png

package com.zy.demo.algorithm;

/**
 * 动态规划
 * @author zy
 */
public class DynamicProgramming {

    /**
     * 求解指定两个字符串的最大公共子字符串
     * @param str1 字符串1
     * @param str2 字符串2
     * @return 最大公共字符串
     */
    public static String getCommonStr(String str1,String str2){
        //字符串分别转字符数组
        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();
        //构建策略集合二维数组(第一行第一列仅用于占位)
        int[][] strategies = new int[c1.length+1][c2.length+1];
        //填充策略集合
        for(int i = 1 ; i <= c1.length ; i++){
            for(int j = 1 ; j <= c2.length ; j++){
                //分阶段、找状态、做决策
                if(c1[i-1] == c2[j-1]){
                    //状态转移(解决某列字符重复相等的问题)
                    strategies[i][j] = strategies[i-1][j-1]+1;
                }
            }
        }
        //定义最大公共字符串长度
        int maxLen = 0;
        //定义索引游标(假设以字符串str1作为参照物)
        int index = 0;
        //遍历策略集合
        for(int i = 0 ; i <= c1.length ; i++){
            for(int j = 0 ; j <= c2.length ; j++){
                if(strategies[i][j] > maxLen){
                    //找最优策略
                    maxLen = strategies[i][j];
                    index = i;
                }
            }
        }
        //最大公共字符串
        StringBuilder commonStr = new StringBuilder();
        //找终止条件(从起始索引开始拼接公共字符串)
        for(int i = index - maxLen ; i < index ; i++){
            commonStr.append(c1[i]);
        }
        return commonStr.toString();
    }
}