算法——动态规划(DP）

谁践踏了优雅 2021-10-18 09:48 443阅读 0赞

**动态规划问题，大致可以通过以下四部分进行解决：**

*  划分阶段：按照问题的时间或空间特征，把问题分为若干个子阶段。（划分后的子阶段一定要是有序的或者是可排序的，否则问题就无法求解。）
 *  状态表示：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。（要满足无后效性。）
 *  状态转移：状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
 *  确定边界：状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

**只有当每个子问题都是离散的，不依赖于其他子问题时，动态规划才管用 。 **

## **最大子序列** ##

**最长公共子序列(Longest Common Subsequence）**:两个序列公共子序列中的最长者，下面简称LCS,可能出现下面两种比较复杂的情况：  
1.可能有多个

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy81OTkwNzU1LTY2NTExMTBlYjdiYWZlMTMucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy82NjYvZm9ybWF0L3dlYnA][]

2.可能有歧义

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy81OTkwNzU1LWJiYTE2NGU5NmIxN2I4ZDcucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81OTgvZm9ybWF0L3dlYnA][]

**步骤：**

*  首先判断两个字符是否相等，如果相等，根据上一个字符匹配的情况的最终值去生成该网格的值。
 *  如果不相等，根据网格的生成情况，获取该网格的前一个或者上一个的最终值进行比较大小后填充。

以此类推，得到**状态转移公式**：

![aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvODkyMzc3LzIwMTgwOC84OTIzNzctMjAxODA4MDMxMDA0MTMxNDEtNjcxNTMyNjgyLnBuZw][]

**实现：**

/**
     * @Classname LargestSubsequence
     * @Description 动态规划——最大子序列
     * @Date 2019/8/12 14:03
     * @Created zzf
     */
    public class LargestSubsequence {
        public static void main(String[] args) {
    
            String str1 = "ADADVANTAGE";
            String str2 = "EDDUCATIONAL";
            int max = 0;
    
            char[] chars1 = str1.toCharArray();
            char[] chars2 = str2.toCharArray();
    
            //生成网格数组
            int[][] arrs = new int[chars1.length + 1][chars2.length + 1];
    
            //核心
            for (int i = 1; i <= chars1.length; i++) {
                for (int j = 1; j <= chars2.length; j++) {
                    //如果字符匹配成功
                    if (chars1[i - 1] == chars2[j - 1]) {
                        //当前网格的值为上一层网格的前一个值+1。
                        print_arr(arrs);
                        arrs[i][j] = arrs[i - 1][j - 1] + 1;
                        System.out.println("*********************************************");
                        print_arr(arrs);
                        System.out.println("*********************************************");
                    } else {
                        print_arr(arrs);
                        //不相等时取左边或者上边两个比较大者
                        arrs[i][j] = arrs[i - 1][j] > arrs[i][j - 1] ? arrs[i - 1][j] : arrs[i][j - 1];
                        System.out.println("---------------------------------------------");
                        print_arr(arrs);
                        System.out.println("---------------------------------------------");
                    }
                }
            }
    
            print_arr(arrs);
            System.out.println("最大公共序列值:" + arrs[chars1.length][chars2.length]);
        }
    
        public static void print_arr(int[][] arrs) {
            for (int i = 0; i < arrs.length; i++) {
                for (int j = 0; j < arrs[0].length; j++) {
                    System.out.print(arrs[i][j] + "   ");
                }
                System.out.println("");
            }
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70][]

## 背包问题 ##

**步骤：**

*  首先判断该商品是否能够放进该空间大小的背包
 *       如果不能：获取上次的最优值
 *       如果能：判断上次的最优值与(本件商品的值)+最优值\[(该大小的背包-本件商品的大小)\]，根据比较结果进行更新当前网格的最优值

以此类推，得到**状态转移公式**：

![201908121605284.png][]

**实现：**

/**
     * @Classname Knapsack
     * @Description 背包问题
     * @Date 2019/8/12 15:02
     * @Created zzf
     */
    public class Knapsack {
    
        public static void main(String[] args) {
            //最大存储
            int MaxS = 13;
            int weight[] = {3, 4, 5, 6};
            int value[] = {4, 5, 6, 7};
            int number = weight.length;
            //生成网格
            int[][] V = new int[number + 1][MaxS + 1];
    
            //商品的下标
            for (int i = 1; i <= number; i++) {
                //背包可存储大小从1~MaxC最大格
                for (int j = 1; j <= MaxS; j++) {
                    //判断该物品是否能够存储进该大小的背包
                    if (weight[i - 1] <= j) {
                        //判断上次存储在该大小的网格的价值是否比(该商品价格)+最优存储((该网格-该商品大小))要小
                        if (V[i - 1][j] < V[i - 1][j - weight[i - 1]] + value[i - 1]) {
                            //更新该网格的最优存储价值
                            V[i][j] = V[i - 1][j - weight[i - 1]] + value[i - 1];
                        } else {
                            //说明此次存储的网格最优存储任然为上次存储的网格值（不更新）
                            V[i][j] = V[i - 1][j];
                        }
                    } else {
                        //不可以
                        //该网格的最优存储为上一次存储的值
                        V[i][j] = V[i - 1][j];
                    }
                }
            }
    
            for (int i = 1; i <= number; i++) {
                for (int j = 1; j <= MaxS; j++) {
                    System.out.print(V[i][j] + "\t");
                }
                System.out.println();
            }
            System.out.println("最存储是：" + V[number][MaxS]);
        }
    
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 1][]

## 总结 ##

*  每种动态规划解决方案都涉及网格
 *  每个单元格都是一个子问题，而状态转移公式就是计算该单元格的最优解
 *  问题可分解成离散子问题时，可以用动态规划解决

[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy81OTkwNzU1LTY2NTExMTBlYjdiYWZlMTMucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy82NjYvZm9ybWF0L3dlYnA]: /images/20211018/d672b4b34e734231aa19e9135114e9e4.png
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy81OTkwNzU1LWJiYTE2NGU5NmIxN2I4ZDcucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81OTgvZm9ybWF0L3dlYnA]: /images/20211018/0a3cddcc1bf541b881f33cfd923afcc1.png
[aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvODkyMzc3LzIwMTgwOC84OTIzNzctMjAxODA4MDMxMDA0MTMxNDEtNjcxNTMyNjgyLnBuZw]: /images/20211018/af5b52e9e4744785abcbd6292cc88084.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70]: /images/20211018/d5403634fff940f1bf1d177b7e33c84b.png
[201908121605284.png]: /images/20211018/1ee5091f043c49aca0c6c33a1ad9e198.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 1]: /images/20211018/7d87ef60b9d741a5a6f2a13132677d51.png