专栏首页爱编码经典算法之动态规划

经典算法之动态规划

原文地址:https://www.cnblogs.com/huststl/p/8664608.html

动态规划(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上。

该三角形第n层有n个数字,例如:

第一层有一个数字:5

第二层有两个数字:8 4

第三层有三个数字:3 6 9

第四层有四个数字:7 2 9 5

最优方案是:5 + 8 + 6 + 9 = 28

注意:上面应该是排列成一个三角形的样子不是竖向对应的,排版问题没有显示成三角形。

状态定义: Fi,j是第i行j列项最大取数和,求第n行Fn,m(0 < m < n)中最大值。

状态转移方程:Fi,j = max{Fi-1,j-1,Fi-1,j}+Ai,jt

import java.util.Scanner;

/**
 * Created by huststl on 2018/3/28 14:24
 * 动态规划题01
 *
 */
public class Dp01 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        long max = 0;
        int[][] dp = new int[n][n];
        dp[0][0] = scan.nextInt();

        for(int i=1;i<n;i++){
            for(int j=0;j<=i;j++){
                int num = scan.nextInt();
                if(j==0){
                    dp[i][j] = dp[i-1][j] + num;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j-1],dp[i - 1][j])+num;
                }
                max = Math.max(dp[i][j],max);
            }
        }
        System.out.println(max);
    }
}

例题2:编辑距离

编辑距离,又称Levenshtein距离(也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。例如将kitten一字转成sitting:sitten (k->s) sittin (e->i) sitting (->g) 所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。给出两个字符串a,b,求a和b的编辑距离。

状态定义:Fi,j表示第一个字符串的前i个字母和第二个字符串的前j个字母需要编辑的次数,求Fn,m,n和m分别是两个字符串的长度。

状态转移方程:当Fi,j-1=Fi-1,j时,Fi,j=Fi,j-1;当Fi,j-1!=Fi-1,j时,Fi,j=min{Fi-1,j-1,Fi,j-1,Fi-1,j}+1.

import java.util.Scanner;

/**
 * Created by huststl on 2018/3/28 14:44
 * 动态规划02
 */
public class dp02 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String aStr = scan.nextLine();
        String bStr = scan.nextLine();
        int aLen = aStr.length();
        int bLen = bStr.length();
        int[][] dp = new int[aLen+1][bLen+1];
        for(int i=0;i<aLen+1;i++){
            dp[i][0] = i;
        }
        for(int i=0;i<bLen+1;i++){
            dp[0][i] = i;
        }
        for(int i=1;i<aLen+1;i++){
            for(int j=1;j<bLen+1;j++){
                if(aStr.charAt(i-1) == bStr.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        System.out.println(dp[aLen][bLen]);
    }
}

例题3:矩阵取数问题

一个N*N矩阵中有不同的正整数,经过这个格子,就能获得相应价值的奖励,从左上走到右下,只能向下向右走,求能够获得的最大价值。例如:3 * 3的方格。

1 3 3 2 1 3 2 2 1

能够获得的最大价值为:11。

import java.util.Scanner;

/**
 * Created by huststl on 2018/3/28 14:55
 * 矩阵取数问题
 */
public class Dp03 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] dp = new int[n+1];
        int[] readMax = new int[n+1];

        for(int i=0;i<n;i++){
            for(int k=1;k<n+1;k++){
                readMax[k] = scan.nextInt();
            }
            for(int j=1;j<n+1;j++){
                dp[j] = Math.max(dp[j],dp[j-1])+readMax[j];
            }
        }
        System.out.println(dp[n]);
    }
}

例题4:背包问题

在N件物品取出若干件放在容量为W的背包里,每件物品的体积为W1,W2……Wn(Wi为整数),与之相对应的价值为P1,P2……Pn(Pi为整数)。求背包能够容纳的最大价值。

import java.util.Scanner;

/**
 * Created by huststl on 2018/3/28 15:06
 * 背包问题
 */
public class Dp04 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int v = scan.nextInt();
        int[] dp = new int[v+1];
        int[] price = new int[n+1];
        int[] weight = new int[n+1];
        long max = 0;
        for(int i=1;i<n+1;i++){
            weight[i] = scan.nextInt();
            price[i] = scan.nextInt();
        }
        for(int i = 1;i<n+1;i++){
            for(int j= v;j>0;j--){
                if(j-weight[i] >= 0){
                    dp[j] = Math.max(dp[j],dp[j-weight[i]]+price[i]);
                }else {
                    dp[j] = dp[i];
                }
            }

        }
        for(int i=0;i<v+1;i++){
            max = max > dp[i]?max:dp[i];
        }
        System.out.println(max);
    }
}

例题5:最长递增子序列

给出长度为N的数组,找出这个数组的最长递增子序列。(递增子序列是指,子序列的元素是递增的) 例如:5 1 6 8 2 4 5 10,最长递增子序列是1 2 4 5 10。

import java.util.Scanner;

/**
 * Created by huststl on 2018/3/28 15:18
 * 最长递增子序列
 */
public class Dp05 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] num = new int[n];
        for(int i=0;i<n;i++){
            num[i] = scan.nextInt();
        }
        double[] dou = new double[n+1];
        dou[0] = Integer.MIN_VALUE;
        dou[1] = num[0];
        int Len = 1;
        int p,r,m;
        for(int i=1;i<n;i++){
            p = 0;
            r = Len;
            while (p<=r){
                m = (p+r)/2;
                if(dou[m] < num[i]){
                    p = m+1;
                }else {
                    r = m-1;
                }
            }
            dou[p] = num[i];
            if(p>Len){
                Len++;
            }
        }
        System.out.println(Len);
     }
}

参考文档

https://www.cnblogs.com/xiaoshen666/p/11014954.html

https://www.cnblogs.com/libra-yong/p/6296356.html

本文分享自微信公众号 - 爱编码(ilovecode),作者:zero

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Netty】ByteBuf (一)

    所有的网路通信都涉及字节序列的移动,所以高效易用的数据结构明显是必不可少的。Netty的ByteBuf实现满足并超越了这些需求。

    用户3467126
  • Spring bean的生命周期

    Spring中Bean的管理是其最基本的功能,根据下面的图来了解Spring中Bean的生命周期:

    用户3467126
  • 经典算法之bitmap算法

    本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景,例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说B...

    用户3467126
  • Hiho Coder 1038 01背包(模板)

           01背包的原型就是有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci,得到的价值是Wi,求将哪些物品装入背包可使获得的价值总和最大。而...

    Ch_Zaqdt
  • Golang Leetcode 956. Tallest Billboard.go

    dp思路 dp方程的键为两个柱子之间的高度差,值为当前高度差情况下,两个柱子的最小高度 状态转移的时候有三种情况,其中后两种可以合并 最后dp[0]保存的...

    anakinsun
  • 利用动态规划求解旅行商问题时空复杂度分析以及相关实验验证

    利用动态规划求解旅行商问题(Travelling Salesman Problem,简称TSP)在之前的推文中已经有了详细的介绍,今天我们要对这个问...

    用户1621951
  • 转载 | 利用动态规划求解旅行商问题(Travelling Salesman Problem)时空复杂度分析以及相关实验验证

    利用动态规划求解旅行商问题(Travelling Salesman Problem,简称TSP)在之前的推文中已经有了详细的介绍,今天我们要对这个问题进行更深一...

    短短的路走走停停
  • dp考试

    a 【问题描述】 ?个物品 ,每个物品都有恰好两。第 ?种物品的体积和价值分别是 ??和??。 背包的体积为 ?,问在不超过背包体积的情况下最多能放进少价值物品...

    attack
  • NYOJ 860 又见01背包(思维)

           刚一看这道题以为是01背包的裸题,TLE了一次后发现这是一道拐了个弯的裸题,题中给的物品重量范围太大了,所以我们可以换种思路,把最大价值求出来,然...

    Ch_Zaqdt
  • 51Nod-1833-环

    ACM模版 描述 ? 题解 图论的问题我没有怎么深入学习,多数都是交给了队友去搞,所以看到这个题时,只知道是图上状压 DPDP,却不知道具体从何入手。 看了题解...

    f_zyj

扫码关注云+社区

领取腾讯云代金券