1.原理

基本思想：问题的最优解如果可以由子问题的最优解推导得到，则可以先求子问题的最优解，在构造原问题的最优解，若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。
使用条件：可分为多个相关子问题，子问题的解被重复使用。
动态规划算法的设计步骤：
1.分析优化解得结构
2.递归的定义最优解的代价
3.自上而下的计算优化解的代价保存，并获得构造最优解的信息
4.根据构造最优解的信息构造优化解。
动态规划特点：
1.把原始问题划分成一系列子问题
2.求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间
3.自底向上地计算。
4.整体问题最优解取决于子问题的最优解（状态转移方程）（将子问题称为状态，最终状态的求解归结为其他状态的求解）

2.实例

1.两个字符串最大的公共字符串

public static String LCS(String str1, String str2){
        /**
         * 基本思路：
         * 1.取一个字符串开始遍历
         * 2.取两个字符串遍历
         */
        StringBuilder sb = new StringBuilder();
        int start = 0, end = 1;
        while (end < str1.length() + 1) {
            if (str2.contains(str1.substring(start, end))) {
                //保证下一步的公共字符串大于上一步公共字符串
                if (sb.length() < end - start) {
                    sb.delete(0, sb.length());
                    sb.append(str1, start, end);
                }
                end++;
            } else {
                start++;
            }
        }
        if (sb.length() == 0) {
            return "-1";
        }
        return sb.toString();
    }