vlambda博客
学习文章列表

聊聊算法--动态规划

既然是聊算法,我们也不必开始就去追求多么的高深复杂,从经典开始,从通俗起步,很多经典算法,比如快排、二分查找、树遍历等,站在经典的肩膀上,往往能看得更远,理解更多,今天来说一下动态规划,属于算法中比较难的点,但深入浅出系列总是有的,我就随便写写,希望能有所助益。

准备:

Idea2019.03/Gradle6.0.1/Maven3.6.3/JDK11.0.4

难度: 新手--战士--老兵--大师

目标:

1.理解并应用动态规划算法

1 定义

动态规划(Dynamic Programming,DP),是运筹学的一个分支,是求解决策过程最优化的过程。用于解决「多阶段决策问题」。有一类活动,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。当各个阶段决策确定后,就组成了一个决策序列,因而也就确定了整个过程的一条活动路线,这个决策的过程是”动态”的。举例,如凑零钱、最短路径、01背包问题等。

可以用DP解决的问题,一定是能将大问题拆成几个小问题,且必须具备两个特征:「无后效性」和「最优子结构」,具体来讲,无后效性是指如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。最优子结构是指大问题的最优解可以由小问题的最优解推出,即子问题也是某个阶段的最优解。

DP的关键在于解决冗余,即减少子问题的重复计算,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。

2 冗余压缩

我们以斐波那契数列问题举例来说明重叠子问题冗余压缩,先写个始祖鸟版(Java):

static int fin(int n){
    if (n ==1 || n==2){
        return 1;
    }
    return fin(n - 1) + fin(n - 2);
}

以上代码,是通过递归来完成,但同时会发现,算法过程存在大量重复计算,分析下时间复杂度,会发现子问题规模是棵二叉树,时间复杂度为O(2^n),例如fin(5)=fin(4)+fin(3),左分支 fin(4)=fin(3)+fin(2),右分支fin(3)=fin(2)+fin(1),如果我们使用一个数组,取名为「备忘录」,来保存子问题的中间状态结果,然后计算子问题时,先去查找数组里面是否已经存在,这样就可以减少重复计算了(Java):

static int fin(int n){
    // 初始化全为0的数组
    int[] temp = new int[n + 1];
    if (n ==1 || n==2){
        return 1;
    }
    // 如果存在,则不必计算
    if (temp[n] != 0){
        return temp[n];
    }
    temp[n] = fin(n - 1) + fin(n - 2);
    return temp[n];
}

以上代码分析: 通过「备忘录」来记录子问题状态,从而减少了计算冗余,如果分析时间复杂度,我们会发现每个子问题只会计算一次,从而为O(n)。并且是「自顶向下」方法,即从目标开始向基线(Base case)计算。

3 状态转移方程

同样是斐波那契数列问题,运用DP来解决,使用「自底向上」的迭代写法,即从基线(Base case)出发向目标计算(Java):

static int fina(int n){
    if (n == 1 || n == 2){
        return 1;
    }
    int[] temp = new int[n + 1];
    temp[1] = temp[2] = 1;
    for (int i = 3; i <= n ; i++) {
        temp[i] = temp[i - 1] + temp[i - 2];
    }
    return temp[n];
}

以上代码分析: 其中的 temp[i] = temp[i-1] + temp[i-2], 即是动态规划中的「状态转移方程」,其中的temp数组即是动态规划表,即「DP table」。如果分析时间复杂度,会发现此迭代写法为O(n),因为每个状态也只计算一次。

考虑一下空间优化?

同时,可以观察到斐波那契数列每次迭代都只使用了前面两个中间结果,所以可以进一步减少空间使用,使空间复杂度为O(1),而上面的动态规划表空间复杂度为O(n),(Java):

static int fibo(int n){
    if (n == 1 || n == 2){
        return 1;
    }
    // 从左到右,左小右大:fir,sec,thd
    int fir = 1,sec = 1,thd = 1;
    for (int i = 3; i <= n ; i++) {
        thd = fir + sec;
        sec = thd;
        fir = sec;
    }
    return thd;
}

做个总结:虽然斐波那契数列问题,不是真正的动态规划例子,因没有找“最优”的过程,但很好的展示了冗余压缩和状态转移方程。另外可见,用备忘录的递归解法已经和迭代的动态规划解法等效,而且动态规划一般都脱离了递归,而是由循环迭代完成计算,这样才能体现阶段选择和状态转移。

4 DP应用

动态规划核心,就是确定每个阶段的「状态」和「选择」,写出「状态转移方程」。

我们先用凑零钱问题来说明DP的思路,需求:钱的面额只有1元、2元和5元,数量无限,如何使用最少的钱币数凑出99元钱。

分析:采用「自顶向下」方法,如果定义f(n)为凑出总额为n的最小数量,那么求f(99)的最后一个“阶段”可以是从f(99-1)+1,f(99-2)+1,f(99-5)+1中做选择,最小的即总数最小(这里有个思考题,即为什么大问题的最优解,一定是从小问题的最优解发展而来?有没有不是这种情况的?这是理解DP的关键,例如要找全校成绩最好的,肯定可以先从班级中找出最好的再比较,但如果说找出全校乒乓球双打最好的两人组,就不可以直接先从班级中找出单打最好的,再取一二名直接组合,毕竟双打还要考虑配合度,所以DP有适用条件,见文章前面定义),从而进一步可以去找前一个阶段f(98),f(97)和f(95),直到base case 处:f(0) 等于0,列出状态转移方程,其中coins={1,2,5}:

按照上面的分析,我们使用「自下而上」的方法,即可以写出DP解法(Java):

static int money(int[] coins,int mount) {
    int[] dp = new int[mount + 1];
    // dp[i]初始化为i,即最多需要i个为1的面额
    for (int i = 0; i < mount + 1; i++) {
        dp[i] = i;
    }
    for (int i = 0; i < mount + 1; i++) {
        for (int coin : coins
        ) {
            if (i - coin < 0continue;
            dp[i] = Math.min(dp[i],dp[i - coin] + 1);
        }
    }
    return dp[mount];
}

以上代码分析:1. dp[i]初始化为i,即最多需要i个为1的面额,作为可行解,并用于后面的状态选择做比较,从而选择最小的;2.双层for循环,外层是目标金额的迭代,内部是coins集合的迭代;3. 外层for循环,需要计算dp[mount]的值,故i < mount + 1;4.这里的base case就是dp[0]=0;

我们用一个图示来描述如何到达f(5)的状态:

聊聊算法--动态规划

如果我们想写个「自上而下」的方法,则可以使用带备忘录的递归写法,可参考上面的斐波那契数列问题,请看官完成,此处略!

再说个最短路径的动态规划:需求:一个n*n的矩阵,每个矩阵点代表经过该点需耗费的精力,从[1,1]走到[n,n]最省力气的路径?每步只能向右或向下走。

分析:如果我们定义dp[i,j] 代表到达点 [i,j] 的最少精力,那肯定是从点 [i-1,j] 或点 [i,j-1]到达,只需选择其中更小的,依次往前推理,前面的任何点都是类似;反过来,我们从基准出发,点 [1,1] 的值为1,到点 [1,2] 和点 [2,1] 都可以从[1,1]加上该点的消耗即得出,这样,我们就可以算出矩阵中所有点的最少消耗。同时,如果使用二维数组dp[][]记录中间计算状态,就可以减少冗余计算了!

上代码(Java):

static int path(int[][] matrix) {
    int horizontal = matrix.length;
    int vertical = matrix[0].length;
    int[][] dp = new int[horizontal][vertical];
    for (int i = 0; i < horizontal; i++) {
        for (int j = 0; j < vertical; j++) {
            if (i -1 < 0 || j -1 <0){
                continue;
            }
            int temp = 0;
            if(i > 0) temp = Math.min(dp[i][j],dp[i - 1][j] + dp[i][j]);
            if(j > 0) temp  = Math.min(dp[i][j],dp[i][j - 1] + dp[i][j]);
            dp[i][j] += temp;
        }
    }
    return dp[horizontal -1][vertical - 1];
}

以上代码分析:1.二维数组实际是一维数组的每个元素为一维数组,故矩阵横纵轴长度需要分开计算;2.当i=0或j=0时,只有一个前置点位;3.该算法属于「自下而上」思路,当然可以有「自顶向下」的解法,请看官思考吧!

「全文完!」


我近期其他文章:

只写原创,敬请关注