动态规划学习笔记

739 阅读11分钟
Everybody's good at something. 
天生我材必有用。

引言

动态规划应该算是算法里比较难以掌握的了,经常是知其然不知其所以然。也是初学者学习算法中的‘拦路虎’,今天本武松将现场直播教学--如何打‘虎’,不对,考虑到老虎乃国家保护动物,本着‘保护动物,人人有责’的原则,换个说法,能用图的就不用文字。


最后希望各位看官老爷看完本文之后,都能够有所收获,最起码能够做到动态规划入门。 本文主要分享了什么是动态规划,动态规划的几个经典案例。

前言

什么是动态规划?

先整点官话 

动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

数学思想:分阶段求解决策问题

 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。 (ps: 记住关键字,后面分析代码时会用到)

别着急,听我慢慢道来。

动态规划总体思路在于解题的步骤,本文大部分代码的实现思想都是基于这个解题步骤,更加的便于理解。

解题步骤

  1. 建立模型
  2. 寻找约束条件
  3. 寻找边界值
  4. 判断是否满足最优性原理
  5. 推出大问题和小问题的递推公式
  6. 建立矩阵表并填写
  7. 计算


话不多说,所有源码均已上传至github:

最长公共子序列

题目

给定两个字符串,求解这两个字符串的最长公共子序列。

比如字符串s1:abcbdab;字符串s2:bdcaba

则这两个字符串的最长公共子序列是:dcba

最长公共子序列长度为4

解析

先构建二阶矩阵表,相当于一个二维数组,这里用dp[i][j]表示,即

d[i][j]表示s1中前i个字符与s2中前j个字符分别组成的两个前缀字符串的最长公共长度.


初始化边界条件,这里 s1长度 m,s2长度n

s1,s2表示占位符,便于边界条件的处理

dp[i][0] = 0; (0 < i < m)

dp[0][j] = 0; (0 < i < n)


注:在这里,我通过不断地对i和j这两个数字量进行不断地求解,直到最终得到答案。这个数字量称之为状态

当出现不匹配情况的时候,则我们取和它相邻的两个点的最大值,即

dp[i][j] = max{dp[i][j-1],dp[i-1][j]}; (s1[i-1] != s2[j-1])

同理的,如果匹配,则在原来基础上加一。即:

dp[i][j] = dp[i-1][j-1] + 1; (s1[i] == s2[j])


ps: 常规 数组索引为0是用来当占位符,便于计算,这里看表可知,可以把s1的 a和s2的b作为边界

呢现在的二阶矩阵表构建完毕,转换成代码如下:

准备 (二维数组的打印)

    private void print(int[][] dp) {
        for (int[] ds : dp) {
            System.out.println(Arrays.toString(ds));
        }
    }

方法

    private int solution(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[][] dp = new int[str1.length][str2.length];
        for (int i = 0; i < str1.length; i++) {
            if (str1[i] == str2[0]){
                dp[i][0] = 1;
            }else{
                dp[i][0] = 0;
            }
        }
        for (int j = 0; j < str2.length; j++) {
            if (str2[j] == str1[0]){
                dp[0][j] = 1;
            }else{
                dp[0][j] = 0;
            }
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                if (str1[i] == str2[j]){
                    dp[i][j] = dp[i-1][j-1] +1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        print(dp);
        int length = 0;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < str1.length; i++) {
            for (int j = 0; j < str2.length; j++) {
                if (dp[i][j] == length && stringBuilder.indexOf(String.valueOf(str1[i])) == -1) {
                    stringBuilder.append(str1[i]);
                }
                length = Math.max(length,dp[i][j]);
            }
        }
        System.out.println(stringBuilder.reverse().toString());
        return length;
    }

前两个for循环构建边界条件,第三个for循环填充二维数组。其实在这里dp[i][j](i,j取max)就是我们要求得长度。第四个for循环,是根据所得进行回溯,获得子序列,这个子序列也就是他的最长公共子串。

测试代码

        LongestCommonSequence longestCommonSubString = new LongestCommonSequence();
        String s1 = "abcbdab";
        String s2 = "bdcaba";
        int res = longestCommonSubString.solution(s1,s2);
        System.out.println(res);

测试结果


最长公共子串

题目

给定两个字符串,求解这两个字符串的最长公共子串。

比如字符串str1:abcbdab;字符串str2:bdcaba

则这两个字符串的最长公共子串是:ab 或者 bd

这里的二阶矩阵表大致思路和求最长公共子序列有点相似,但是注意:

因为最长公共子串要求必须在原串中是连续的,所以一但某处出现不匹配的情况,此处的值就重置为0。即:

dp[i][j] = 0; (str1[i] != str2[j])

完整公式

  1. dp[i][0] = 0; (0<=i<=m) 
  2. dp[0][j] = 0; (0<=j<=n) 
  3. dp[i][j] = dp[i-1][j-1] +1; (str1[i] == str2[j]) 
  4. dp[i][j] = 0; (str1[i] != str2[j])

完整二阶矩阵表


呢现在的二阶矩阵表构建完毕,转换成代码如下:

准备

最长公共子串结果拼接 (这里的str 传 str1或者str2任意一个即可)

    private String resJoint(String str, int x, int y) {
        StringBuilder stringBuilder = new StringBuilder();
        while (x >= 0 && y >= 0) {
            stringBuilder.append(str.charAt(y--));
            --x;
        }
        return stringBuilder.reverse().toString();
    }

二维数组打印

    private void print(int[][] dp) {
        for (int[] ds : dp) {
            System.out.println(Arrays.toString(ds));
        }
    }

方法一

    private String solution(String str1, String str2) {
        int[][] dp = new int[str1.length()][str2.length()];
        char[] str1Chars = str1.toCharArray();
        char[] str2Chars = str2.toCharArray();

        for (int i = 0; i < str1Chars.length; i++) {
            if (str1Chars[i] == str2Chars[0]) {
                dp[i][0] = 1;
            } else {
                dp[i][0] = 0;
            }
        }
        for (int j = 0; j < str2Chars.length; j++) {
            if (str2Chars[j] == str1Chars[0]) {
                dp[0][j] = 1;
            } else {
                dp[0][j] = 0;
            }
        }
        for (int i = 1; i < str1Chars.length; i++) {
            for (int j = 1; j < str2Chars.length; j++) {
                if (str1Chars[i] == str2Chars[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        print(dp);
        int max = dp[0][0];
        //--> j
        int x = 0;
        // --> i
        int y = 0;
        for (int i = 0; i < str1Chars.length; i++) {
            for (int j = 0; j < str2Chars.length; j++) {
                if (dp[i][j] > max) {
                    max = dp[i][j];
                    y = i;
                    x = j;
                }
            }
        }
        System.out.println(max + "," + x + "," + y);

        return resJoint(str1, x, y);
	}

这里只分析第四个for循环,根据结果,求二阶矩阵中的最大值,由表可知,最长公共子串不是唯一的。这里只需要求出任意一组即可。如果需要全部罗列,只需要将x,y当数组存储,然后根据索引就可以拿出所有的最长公共子串了。

方法二

其实二阶矩阵表我们可以找出规律,将其转换为求二阶矩阵的最大地址对角线问题

    private String solution2(String str1, String str2) {
        char[] str1Chars = str1.toCharArray();
        char[] str2Chars = str2.toCharArray();
        int x = 0;
        int y = 0;
        int index = 0;
        int max = 0;
        //列
        int row = 0;
        //行
        int col = str2Chars.length - 1;
        //计算矩阵中的每一条斜对角线上的值
        while (row < str1Chars.length) {
            int i = row;
            int j = col;
            while (i < str1Chars.length && j < str2Chars.length) {
                if (str1Chars[i] == str2Chars[j]) {
                    if (++index > max) {
                        max = index;
                        x = j;
                        y = i;
                    }
                } else {
                    index = 0;
                }
                i++;
                j++;
            }
            if (col > 0) {
                --col;
            } else {
                ++row;
            }
        }
        System.out.println(max + "," + x + "," + y);
        return resJoint(str1, x, y);
    }

测试代码

        LongestCommonSubString longestCommonSubString = new LongestCommonSubString();
        String s1 = "abcbdab";
        String s2 = "bdcaba";
        String res = longestCommonSubString.solution(s1, s2);
        System.out.println("最长公共子串为:" + res);
       String res2 = longestCommonSubString.solution2(s1, s2);
       System.out.println("最长公共子串为:" + res2);

测试结果

方法一


方法二


最长递增子序列

题目

 最长递增子序列是指找到一个给定序列的最长子序列的长度,使得子序列中的所有元素单调递增。

 例如:{ 3,5,7,1,2,8 } 的 LIS 是 { 3,5,7,8 },长度为 4。

解析

这个问题和前两个问题又不太一样,需要自己和自己比较。

当 {3}的时候 LIS {3},长度 1

当 {3,5}的时候 LIS {3,5},长度 2

当 {3,5,7}的时候 LIS {3,5,7},长度 3

当 {3,5,7,1}的时候 LIS {3,5,7},长度 3

...

这里我们可以把原问题分解成 子问题来解决。(文章开头提过)

先考虑边界情况. F(1) = 1; i = 1;

根据上面可总结出公式 

i表示 当前数组的索引,j表示当前数组的子数组的索引

F[i] = max{1,F[j]+1} ( F[j]<F[i] && j<i)

公式总结出来了,根据公式将其转换成代码,具体实现如下:

    private int solution(int[] nums){
        //推公式
        //F[i] = max{1,F[j]+1|aj<ai && j<i}
        int[] F = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            F[i] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j] < nums[i] && F[i] < F[j] + 1) {
                    F[i] = F[j] + 1;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if(F[i] > max) {
                max = F[i];
            }
            System.out.println("F[" + i + "] = " + F[i]);
        }
        System.out.println();
        return max;
    }

第一个for循环初始化 公式数组,将其全部置为1.

第二个for循环根据所得的公式将数组填满

第三个for循环获取满足条件的索引及最大值

测试代码

        int[] nums = { 3,5,7,1,2,8 };
        int res = new LongestIncreasingSubSequence().solution(nums);
        System.out.println(res);

测试结果

根据打印log可以看出,1 - 2 -3 -4是连贯的,这说明 其对应的索引就是该问题的LIS

即{3,5,7,8}


当然 最长递减子序列的实现也就很容易了。

最大子序列和

题目

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 

例如 [-2,1,-3,4,-1,2,1,-5,4], 

连续子数组 [4,-1,2,1] 的和最大,为 6。

解析

 这道题的求解思路和求最长递增子序列。这里直接罗列出状态转移方程式了:

dp[0] = nums[i]; (i = 0) 

dp[i] = dp[i-1]>=0 ? dp[i-1]+nums[i] : nums[i] (i > 1)

具体实现如下:

private int solution(int[] nums){
	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	for (int i = 1; i < nums.length; i++) {
		if(dp[i - 1] >= 0) {
			dp[i] = dp[i - 1] + nums[i];
		}else {
			dp[i] = nums[i];
		}
		System.out.println("dp[" + i  + "] = " + dp[i]);
	}
	int res = dp[0];
	for (int i = 1; i < dp.length; i++) {
		if(dp[i] > res) {
			res = dp[i];
		}
	}
	return res;
}

当然还有一种更简单的解法只需要一个for循环就可以解决了,我只需要假设一个理想最大子序列res,然后遍历数组,当遍历值是正的,说明是增益的,加上,然后每次取max就可以了。

    private int solution2(int[] nums){
        int res = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            res = Math.max(res, sum);
        }
        return res;
    }

测试代码

        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int res = new MaxSubsequenceSum().solution(nums);
        System.out.println("最大子序列和为:" + res);

测试结果


根据输出的结果可以看到子问题的每一种情况

进阶--01背包

题目

01背包 问题可以说是再经典不过了。

 假设有N件物品和一个容量为V的背包。第i件物品的体积是v[i],价值是p[i],将哪些物品装入背包可使价值总和最大?

例题

N = 4, V = 8


解析

每一种物品都有两种可能即放入背包或者不放入背包。 

可以用dp[i][j]表示第i件物品放入容量为j的背包所得的最大价值,则状态转移方程可以推出。

边界条件

dp[i][0] = dp[0][j] = 0 (i > 0,j > 0) 

当背包容量小于物品重量时 即j < v[i],则装不进去,保持原状即可

dp[i][j] = dp[i-1][j] (j < v[i]) 

当能装下的时候,则需要考虑装入之前是什么状态,肯定是v[i-1][j-v[i]],当前物品的价值是p[i]

dp[i][j] = max{dp[i-1][j], dp[i-1][j-v[i]]+p[i]} (j >= v[i]) 

初始化二阶矩阵


根据公式填表


则dp[4][8] = 10,也就是装入物品的最大价值,但是装进去的是哪一些呢,则需要进行回溯了。

dp(i,j)=dp(i-1,j)   说明没有选择第i 个商品,则回到dp(i-1,j); 

dp(i,j)=dp(i-1,j-v(i))+p(i) 说明装了第i个商品,该商品是最优解组成的一部分,随后我们得回到装该商品之前,即回到dp(i-1,j-v(i)); 一直遍历到i=0结束为止.

略low的表示一下

dp[4][8] != dp[3][8] 并且 dp[4][8] =dp[3][8 - 5] + 6 ===> d[3][3]

说明第四个商品选中;

dp[3][3] = dp[2][3] 第三个商品没有被选中;

dp[2][3]!=dp[1][3]并且 dp[2][3] = dp[1][4-4] + 4 ====> dp[1][0]

说明第二件商品被选中;

dp[1][0] == dp[0][0]

说明第一件商品没有被选中。

具体实现代码如下

    private int solution(int[] v, int[] p, int c) {
        int[][] dp = new int[v.length][c + 1];
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < c + 1; j++) {
                if (j < v[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + p[i]);
                }
            }
        }
        print(dp);
        int[] items = new int[v.length];
        situation(items, v, p, dp, v.length - 1, c);
        System.out.println("回溯选中的物品:(1表示选中)");
        System.out.println("体积:" + Arrays.toString(v));
        System.out.println("价格:" + Arrays.toString(p));
        System.out.println("选中:" + Arrays.toString(items));
        return dp[v.length - 1][c];
    }

回溯方法

    private void situation(int[] items, int[] v, int[] p, int[][] dp, int i, int j) {
        if (i > 0) {
            if (dp[i][j] == dp[i - 1][j]) {
                situation(items, v, p, dp, i - 1, j);
            } else if (j - v[i] >= 0 && dp[i][j] == dp[i - 1][j - v[i]] + p[i]) {
                items[i] = 1;
                situation(items, v, p, dp, i - 1, j -v[i]);
            }
        }
    }

打印数组 print (参考上面)

测试代码

        // 0 占位
        int[] v = {0, 2, 3, 4, 5};
        int[] p = {0, 3, 4, 5, 6};
        int c = 8;
        BackPack01 backPack01 = new BackPack01();
        int max = backPack01.solution(v, p, c);
        System.out.println("当体积为" + c + "时,最大价值为" + max);

测试结果


end


您的点赞和关注是对我最大的支持,谢谢!