动态规划——是什么/怎么做 是什么 怎么做

发表于

是什么

动态规划不是一种算法， 而是一种算法思想。通过将复杂问题拆分成子问题，再通过求解子问题的解进而得到原问题的解。

给定一个问题，我们通过解其不同的部分(即子问题)，再根据子问题的解解出原有问题的解。应用算法的思想解决问题的可行性，对于子问题和原问题的关系以及子问题的之间的关系有一定要求，即最优子结构和重复子问题

最优子结构

最优子结构是子问题和原问题之间的关系。

动态规划解决的是一些问题的最优解。通过将原问题拆解成不同部分的子问，然后递归的寻找每个子问题的最优解，最后通过一定的数学方法对子问题的最优解进行组合得出最终解。

将子问题的解进行组合可以得到原问题的最终解这是动态规划可行性的关键。在题解中一般是通过状态转移方程描述这种组合。例如原问题的解为f(n)，其中f(n)也叫状态。状态转移方程f(n) = f(n-1) + f(n-2)描述了子问题和原问题之间的组合关系。同时在原问题的求解过程中， 不同选择可能对应子问题之间不同的组合关系(n=2k和n=2k+1在这里表示不同的选择，对应了子问题的不同组合)：

1
2
3
scss复制代码            f(n−1)+f(n−2)  n=2k
    f(n)={  
            f(n−1)         n=2k+1

找到了最优子结构，也就能推导出一个状态转移方程，通过状态转移方程可以很快得出问题的递归实现。

重复子问题

重复子问题是指子问题和子问题之间的关系。当我们在递归的寻找某个子问题的最优解的时候会重复遇到更小子问题。这些问题会导致重复计算，动态规划保证每个重复子问题只会被计算一次。再解决重复计算问题时，一般通过记忆化递归法：若能事先确定子问题的范围就可以建表存储子问题的答案。

解决动态规划的核心： 找出子问题和原问题的关系

动态规划算法中关于最优子结构和重复子问题的理解的关键点：

  • 证明问题的方案中包含一种选择，选择之后留下一个或多个子问题
  • 设计子问题之间的组合关系，即状态状态转移方程
  • 证明子问题是重叠的，并且通过记忆化存储

怎么做

1
2
3
4
5
6
ini复制代码举例：
描述： 给定一个无序数组，找到其中长度最大的递增子序列
示例：
    输入: [10,9,2,5,3,7,101,18]
    输出: 4
    解释: 最长的上升子序列是 [2,3,7,101]，它的长度是4。

能否将问题规模减小，一些典型的减小方式是动态规划分类的依据。例如线性，区间，树形等。这里考虑数组常用的两种方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
css复制代码- 每次减少一半：个子问题[10,9,2,5]和[3,7,101,18]的最优解是[2,5]和[3,7,101]。这两个子问题的最优解没法通过一定的组合得到原问题的最优解[2,3,7,101]
- 每次减少一个：记f[n]为以第n个元素结尾的最长子序列，每次减少一个，将原问题分解成f[n-1], f[n-2]...f[1]共n-1个问题。n-1 = 7个问题的答案如下：
    [10, 9, 2, 5, 3, 7, 101] -> [2, 5, 7, 101]
    [10, 9, 2, 5, 3, 7] -> [2, 5, 7]
    [10, 9, 2, 5, 3] -> [2, 3]
    [10, 9, 2, 5] -> [2, 5]
    [10, 9, 2] -> [2]
    [10, 9] -> [9]
    [10] -> [10]
    已经有了7个子问题的最优解，可以发现通过一种组合方式可以得到原问题的最优解。f[6]的结果[2, 5, 7]， 7 < 18,同时长度也是f[1]~f[7]中结尾元素小于18的结果中长度最长的。f[7]的长度为4，虽然长度是最长的，但是结尾元素101大于18，无法组合成原问题的解。以上的组合方式可以归纳成一个状态转移方程：
    f[n]= maxf[i] + 1 其中i<n且a[i]<a[n]
- 总结：解决动态规划问题最难的两个点在于：
    - 如何定义f[n]
    - 如何通过f[1], f[2]...f[n-1]推导出f[n], 即如何推导出状态转移方程
  1. 递归

有了状态转移方程，实际上可以通过递归的方式直接实现了

1
2
3
4
5
6
7
8
9
golang复制代码func find(arr []int, len int) (res int){
    res := 1
    for i :=0; i<len; i++ {
        if (arr[i] < arr[len]) {
            res = max(res, find(arr , i) + 1)
        }
    }
    return res
}
  1. 自上向下(记忆法）

递归方法的求解过程中会存在大量的重复计算，记忆法通过记录在求解f[1], f[2]…过程中的结果，将结果保存在一个表中， 在后续求解子问题的时候，如果遇到之前就已得出的子问题的结果，就拿来直接使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
golang复制代码func find(arr []int, len int, dp []int)(res int) {
    if (dp[len] != -1 ){
        return dp[len]
    }
    res := 1
    for i :=0; i<len; i++ {
        if (arr[i] < arr[len]) {
            res = max(res, find(arr , i) + 1)
        }
    }
    dp[len] = res
    return res
}
  1. 自底向上(迭代）

由于有状态转移方程的存在， 我们可以通过增加问题规模的方式，一步步的靠近原问题的规模。在这过程中，需要记录每个问题的解来避免重复计算

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%