java-动态规划算法学习笔记

vlambda
2020-04-29

java-动态规划算法学习笔记

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。在面试笔试中动态规划也是经常作为考题出现，其中较为简单的DP题目我们应该有百分之百的把握顺利解决才可以。

动态规划定义

动态规划实际上是一类题目的总称，并不是指某个固定的算法。动态规划的意义就是通过采用递推（或者分而治之）的策略，通过解决大问题的子问题从而解决整体的做法。动态规划的核心思想是巧妙的将问题拆分成多个子问题，通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题，从而用类似递推迭代的方法解决要求的问题。

动态规划的解题核心

动态规划的解题核心主要分为两步：

第一步：状态的定义
第二步：状态转移方程的定义

在这里，我们为了避免混淆用“状态”这个词来替代“问题”这个词。“问题”表示的含义类似：题目、要求解的内容、题干中的疑问句这样的概念。状态表示我们在求解问题之中对问题的分析转化。

第一步：状态的定义

有的问题过于抽象，或者过于啰嗦干扰我们解题的思路，我们要做的就是将题干中的问题进行转化（换一种说法，含义不变）。转化成一系列同类问题的某个解的情况，比如说：

题目：求一个数列中最大连续子序列的和。

我们要将这个原问题转化为：

状态定义：Fk是第k项前的最大序列和，求F1～FN中最大值。

通过换一种表述方式，我们清晰的发现了解决问题的思路，如何求出F1～FN中的最大值是解决原问题的关键部分。上述将原问题转化成另一种表述方式的过程叫做：状态的定义。这样的状态定义给出了一种类似通解的思路，把一个原来毫无头绪的问题转换成了可以求解的问题。

第二步：状态转移方程的定义

在进行了状态的定义后，自然而然的想到去求解F1～FN中最大值。这也是状态定义的作用，让我们把一个总体的问题转化成一系列问题，而第二步：状态转移方程的定义则告诉我们如何去求解一个问题，对于上述已经转换成一系列问题我们要关注的点就在于：如何能够用前一项或者前几项的信息得到下一项，这种从最优子状态转换为下一个最优状态的思路就是动态规划的核心。对于上面的例子题目来说，状态转移方程的定义应该是：

Fk=max{Fk-1+Ak,Ak} Fk是前k项的和，Ak是第k项的值

仔细思考一番，我们能够得到这样的结论，对于前k个项的最大子序列和是前k-1项的最大子序列和Fk与第k项的和、或者第k项两者中较大的。如果大家还是不能理解这个原理建议用演算纸自己计算一番，这里就不过多赘述了。这种状态转移的思路就是DP的核心。

动态规划的应用场景

看过了如何去使用动态规划，那么随之而来的问题就在于：既然动态规划不是某个固定的算法，而是一种策略思路，那么什么时候应该去使用什么时候不能用呢？答案很简短：

对于一个可拆分问题中存在可以由前若干项计算当前项的问题可以由动态规划计算。

例题1: 三角形最大(最小)路径和

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大(最小)值。每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

解题思路: 1、根据原始三角形的高度初始化一个二维结果数组。

2、将原始三角形最低层的数值初始化到二维结果数组的最低层，即最低层的结果路径和。

3、取最底层的上一层的数值。最底层第j个和第j+1个数值中取最大值，加上上一层的第j个数值就是上一层第j个元素的从下到上的最大路径和。

4、不断循环上一步的计算，直到计算到最上层的结果，就是该三角形的最大路径和。

5、如果是求三角形最小路径和，将第三步中取最大值换成取最小值即可。

java代码如下:

/**
 * 三角形数组最大(最小)路径和计算
 * 最小路径和 dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+row.get(i)
 * 最大路径和 dp[i][j]=Math.max(dp[i+1][j],dp[i+1][j+1])+row.get(i)
 **/
public static int fixTriangleTotal(List<List<Integer>> triangle) {
    /**三角形的高度**/
    int height = triangle.size();
    int[][] dp = new int[height][height];
    /**三角形最后一行的数值**/
    List<Integer> lastRow = triangle.get(height - 1);
    for (int i = 0; i < height; i++) {
        dp[height - 1][i] = lastRow.get(i);
    }
    /**从下往上数第二行开始计算**/
    for (int i = height - 2; i >= 0; --i) {
        List<Integer> row = triangle.get(i);
        for (int j = 0; j < i + 1; ++j) {
            dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row.get(j);
        }
    }
    return dp[0][0];
}

测试

/**三角形数组最大(最小)路径和计算**/
List<Integer> list1 = Arrays.asList(1, 0, 0);
List<Integer> list2 = Arrays.asList(1, 4, 0);
List<Integer> list3 = Arrays.asList(1, 5, 6);
List<Integer> list4 = Arrays.asList(4, 9, 6, 7);
List<List<Integer>> totalList = new ArrayList<>();
totalList.add(list1);
totalList.add(list2);
totalList.add(list3);
totalList.add(list4);
System.out.println(fixTriangleTotal(totalList));

例题2:最长上升子序列的长度

给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入: [1,10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

解题思路: 1、根据原始数组，初始化结果数组。

2、结果数组记录的是到目前索引位为止，前面元素的最长上升子序列的长度。并与前一索引位的最长上升子序列长度取最大值。

3、遍历原始数组，即可得到结果。

java代码如下:

public static int longestSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    /**初始化dp[]**/
    int[] dp = new int[nums.length];
    /**数组全部填充1**/
    Arrays.fill(dp, 1);
    /**最长子序列的长度**/
    int max = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

测试

/**最长上升子序列的长度**/
System.out.println("最长上升子序列的长度");
int[] nums = {10, 1, 2, 10, 3, 6, 4, 7, 11};
System.out.println(longestSubArray(nums));

小结

动态规划的核心思想是巧妙的将问题拆分成多个子问题，通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题，从而用类似递推迭代的方法解决要求的问题。

相关代码 https://gitee.com/liulanqi/algorithm.git

vlambda博客
学习文章列表