精华内容
下载资源
问答
  • 实验要求:分别用伪代码或流程图或步骤分析图描述利用动态规划、贪心策略、回溯法的算法解决方案,再用程序实现,计算时间复杂度,记录最终测试数据和测试结果,运行时间。 旅行商问题 问题描述:给定一个的整数矩阵...

    实验四:算法综合练习

    第一次写博客,写的不好,大家如果觉得有用就三连一下/手动狗头
    实验目的:掌握回溯算法的设计思想、具体实现和时间复杂度分析。同时复习动态规划算法、贪心算法。
    实验要求:分别用伪代码或流程图或步骤分析图描述利用动态规划、贪心策略、回溯法的算法解决方案,再用程序实现,计算时间复杂度,记录最终测试数据和测试结果,运行时间。

    旅行商问题
    问题描述:给定一个的整数矩阵,你要写一个程序来计算出最小权值。一条路径从列1(第一列)的任意位置开始,包括一系列的移动,最终抵达列(最后一列)。每一步均由列到列的相邻行(水平或对角)。矩阵的第一行和最后一行(行1和行)认为是相邻的,也就是说矩阵是环绕的,就像一个水平的圆柱体。合法的移动图示如下。
    在这里插入图片描述

    路径的权重就是矩阵中遍历到的所有个单元的整数值之和。例如,两个不同的矩阵如下图所示(仅最后一行的数字略有不同)。两个矩阵的最短路径如图所示。注意,右边矩阵最短路径利用了最上一行和最下一行相邻的特性。
    在这里插入图片描述

    要求:分别用动态规划算法、贪心策略、回溯法编程实现并分析。
    输入格式:
    第1行包含两个整数表示矩阵的维数:行和列,以及下面的个整数。输入的整数按行排列,即输入的第一行个整数为矩阵的第一行,第二行个整数为矩阵的第二行,以此类推。一行中的整数由一个或多个空格隔开。
    注意:行数范围,列数范围,不会存在超过30位整数表示范围的路径权值。
    输出格式:两行,第一行表示一条最小权重路径,第二行表示输出路径的权重值。路径由n个整数组成(由一个或多个空格隔开)表示最小路径的行号。如果有多于一条路径的权重为最小,则按字典顺序输出最小的一组。
    样例输入1:在这里插入图片描述

    样例输出1:
    在这里插入图片描述

    样例输入2:
    在这里插入图片描述

    样例输出2:
    在这里插入图片描述

    其他要求:构造大样本数据,测试运行结果和运行时间(可选,非必须)。可在OJ平台上测试。分析你设计的三种算法的时间复杂度。

    先上代码

    #include<stdio.h>
    #include<stdlib.h>
    
    int main()
    {
        int n, m;//m为行数,n为列数
        scanf("%d %d\n", &m, &n);
        int sum[100][100]{0};//记录每个格子的最短路劲长度
        int number[100][100]{0};//记录输入格子的长度
        int sign[100][100]{0};//记录每个格子最短路径的走向
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &number[i][j]);
                if (j == n - 1) {
                    sum[i][j] = number[i][j];
                }
            }
        }
        int min;
        for (int i = n-2; i >=0; i--) {
            min = 0;
            for (int j = 0; j < m; j++) {
                if (j == 0) {
                    if (number[j][i] + sum[m - 1][i+1] <= number[j][i] + sum[j][i+1]) {
                        min = number[j][i] + sum[m - 1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min >number[j][i] + sum[j + 1][i+ 1]) {
                        min = number[j][i] + sum[j + 1][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
                else if (j == m - 1) {
                    if (number[j][i] + sum[j-1][i + 1] <= number[j][i] + sum[j][i + 1]) {
                        min = number[j][i] + sum[j-1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min > number[j][i] + sum[0][i + 1]) {
                        min = number[j][i] + sum[0][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
                else {
                    if (number[j][i] + sum[j -1][i + 1] <= number[j][i] + sum[j][i + 1]) {
                        min = number[j][i] + sum[j - 1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min > number[j][i] + sum[j+1][i + 1]) {
                        min = number[j][i] + sum[j+1][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
               
            }
        }
        /*这边是检查用的*/
        //for (int i = 0; i < m; i++) {
        //    for (int j = 0; j < n; j++) {
        //        printf("%d ", sum[i][j]);
        //    }
        //    printf("\n");
        //}
        //for (int i = 0; i < m; i++) {
        //    for (int j = 0; j < n; j++) {
        //        printf("%d ", sign[i][j]);
        //    }
        //    printf("\n");
        //}
         min=sum[0][0];
        int x = 0;//记下最小路径的行号
        for (int i = 0; i < m; i++) {
            if (min > sum[i][0]) {
                min = sum[i][0];
                x = i;
            }
        }
        min = x;
        for (int i = 0; i < n; i++) {
            printf("%d ", x + 1);
            if (sign[x][i] == 1) {
                if (x == 0) {
                    x = m - 1;
                }
                else {
                    x--;
                }
            }
            else if (sign[x][i] == -1) {
                if (x == m - 1) {
                    x = 0;
                }
                else {
                    x++;
                }
            }
        }
        printf("\n%d", sum[min][0]);
    }
    

    主要代码分析

    首先主要用到的思想是从n-1的数字开始看,分别计算n-2列的数字加上他对应的上中下的n-1的数字,最后再对比一下,小的就储存到sum二维数组里面,并且将他下一步究竟是这么走的储存到sign二维数组里面。以此类推直到到第0列。

        for (int i = n-2; i >=0; i--) {
            min = 0;
            for (int j = 0; j < m; j++) {
                if (j == 0) {
                    if (number[j][i] + sum[m - 1][i+1] <= number[j][i] + sum[j][i+1]) {
                        min = number[j][i] + sum[m - 1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min >number[j][i] + sum[j + 1][i+ 1]) {
                        min = number[j][i] + sum[j + 1][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
                else if (j == m - 1) {
                    if (number[j][i] + sum[j-1][i + 1] <= number[j][i] + sum[j][i + 1]) {
                        min = number[j][i] + sum[j-1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min > number[j][i] + sum[0][i + 1]) {
                        min = number[j][i] + sum[0][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
                else {
                    if (number[j][i] + sum[j -1][i + 1] <= number[j][i] + sum[j][i + 1]) {
                        min = number[j][i] + sum[j - 1][i + 1];
                        sign[j][i] = 1;
                        sum[j][i] = min;
                    }
                    else {
                        min = number[j][i] + sum[j][i + 1];
                        sign[j][i] = 0;
                        sum[j][i] = min;
                    }
                    if (min > number[j][i] + sum[j+1][i + 1]) {
                        min = number[j][i] + sum[j+1][i + 1];
                        sign[j][i] = -1;
                        sum[j][i] = min;
                    }
                }
               
            }
        }
    

    运行结果

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 并且动态规划这种通过空间换取时间的算法思想在实际工作中也会被频繁用到,这篇文章目的主要是解释清楚什么是动态规划,还有就是面对一道动态规划问题,一般思考步骤以及其中注意事项等等,最后通过几道题目...

    动态规划问题一直是算法面试当中的重点和难点,并且动态规划这种通过空间换取时间的算法思想在实际的工作中也会被频繁用到,这篇文章的目的主要是解释清楚 什么是动态规划,还有就是面对一道动态规划问题,一般的 思考步骤 以及其中的注意事项等等,最后通过几道题目将理论和实践结合。

     

    什么是动态规划

    如果你还没有听说过动态规划,或者仅仅只有耳闻,或许你可以看看 Quora 上面的这个 回答

    有了四步解题法模板,再也不害怕动态规划!

    How to explain dynamic

    用一句话解释动态规划就是 “记住你之前做过的事”,如果更准确些,其实是 “记住你之前得到的答案”。

    我举个大家工作中经常遇到的例子。

    在软件开发中,大家经常会遇到一些系统配置的问题,配置不对,系统就会报错,这个时候一般都会去 Google 或者是查阅相关的文档,花了一定的时间将配置修改好。

    过了一段时间,去到另一个系统,遇到类似的问题,这个时候已经记不清之前修改过的配置文件长什么样,这个时候有两种方案,一种方案还是去 Google 或者查阅文档,另一种方案是借鉴之前修改过的配置,第一种做法其实是万金油,因为你遇到的任何问题其实都可以去 Google,去查阅相关文件找答案,但是这会花费一定的时间,相比之下,第二种方案肯定会更加地节约时间,但是这个方案是有条件的,条件如下:

    • 之前的问题和当前的问题有着关联性,换句话说,之前问题得到的答案可以帮助解决当前问题
    • 需要记录之前问题的答案

    当然在这个例子中,可以看到的是,上面这两个条件均满足,大可去到之前配置过的文件中,将配置拷贝过来,然后做些细微的调整即可解决当前问题,节约了大量的时间。

    不知道你是否从这些描述中发现,对于一个动态规划问题,我们只需要从两个方面考虑,那就是 找出问题之间的联系,以及 记录答案,这里的难点其实是找出问题之间的联系,记录答案只是顺带的事情,利用一些简单的数据结构就可以做到。

     

    思考动态规划问题的四个步骤

    一般解决动态规划问题,分为四个步骤,分别是

    • 问题拆解,找到问题之间的具体联系
    • 状态定义
    • 递推方程推导
    • 实现

    这里面的重点其实是前两个,如果前两个步骤顺利完成,后面的递推方程推导和代码实现会变得非常简单。

    这里还是拿 Quora 上面的例子来讲解,“1+1+1+1+1+1+1+1” 得出答案是 8,那么如何快速计算 “1+ 1+1+1+1+1+1+1+1”,我们首先可以对这个大的问题进行拆解,这里我说的大问题是 9 个 1 相加,这个问题可以拆解成 1 + “8 个 1 相加的答案”,8 个 1 相加继续拆,可以拆解成 1 + “7 个 1 相加的答案”,… 1 + “0 个 1 相加的答案”,到这里,第一个步骤 已经完成。

    状态定义 其实是需要思考在解决一个问题的时候我们做了什么事情,然后得出了什么样的答案,对于这个问题,当前问题的答案就是当前的状态,基于上面的问题拆解,你可以发现两个相邻的问题的联系其实是 后一个问题的答案 = 前一个问题的答案 + 1,这里,状态的每次变化就是 +1。

    定义好了状态,递推方程就变得非常简单,就是 dp[i] = dp[i - 1] + 1,这里的 dp[i] 记录的是当前问题的答案,也就是当前的状态,dp[i - 1] 记录的是之前相邻的问题的答案,也就是之前的状态,它们之间通过 +1 来实现状态的变更。

    最后一步就是实现了,有了状态表示和递推方程,实现这一步上需要重点考虑的其实是初始化,就是用什么样的数据结构,根据问题的要求需要做那些初始值的设定。

    public int dpExample(int n) {
        int[] dp = new int[n + 1];  // 多开一位用来存放 0 个 1 相加的结果
    
        dp[0] = 0;      // 0 个 1 相加等于 0
    
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] + 1;
        }
    
        return dp[n];
    }
    

    你可以看到,动态规划这四个步骤其实是相互递进的,状态的定义离不开问题的拆解,递推方程的推导离不开状态的定义,最后的实现代码的核心其实就是递推方程,这中间如果有一个步骤卡壳了则会导致问题无法解决,当问题的复杂程度增加的时候,这里面的思维复杂程度会上升。

    接下来我们再来看看 LeetCode 上面的几道题目,通过题目再来走一下这些个分析步骤。

     

    题目实战

    爬楼梯

    但凡涉及到动态规划的题目都离不开一道例题:爬楼梯(LeetCode 第 70 号问题)。

    题目描述

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

    注意:给定 n 是一个正整数。

    示例 1:

    输入:2
    输出:2
    解释: 有两种方法可以爬到楼顶。
    
    1. 1 阶 + 1 阶
    2. 2 阶
    

    示例 2:

    输入:3
    输出:3
    解释: 有三种方法可以爬到楼顶。
    
    1. 1 阶 + 1 阶 + 1 阶
    2. 1 阶 + 2 阶
    3. 2 阶 + 1 阶
    

    题目解析

    爬楼梯,可以爬一步也可以爬两步,问有多少种不同的方式到达终点,我们按照上面提到的四个步骤进行分析:

    • 问题拆解

      我们到达第 n 个楼梯可以从第 n – 1 个楼梯和第 n – 2 个楼梯到达,因此第 n 个问题可以拆解成第 n – 1 个问题和第 n – 2 个问题,第 n – 1 个问题和第 n – 2 个问题又可以继续往下拆,直到第 0 个问题,也就是第 0 个楼梯 (起点)

    • 状态定义

      “问题拆解” 中已经提到了,第 n 个楼梯会和第 n – 1 和第 n – 2 个楼梯有关联,那么具体的联系是什么呢?你可以这样思考,第 n – 1 个问题里面的答案其实是从起点到达第 n – 1 个楼梯的路径总数,n – 2 同理,从第 n – 1 个楼梯可以到达第 n 个楼梯,从第 n – 2 也可以,并且路径没有重复,因此我们可以把第 i 个状态定义为 “从起点到达第 i 个楼梯的路径总数”,状态之间的联系其实是相加的关系。

    • 递推方程

      “状态定义” 中我们已经定义好了状态,也知道第 i 个状态可以由第 i – 1 个状态和第 i – 2 个状态通过相加得到,因此递推方程就出来了 dp[i] = dp[i - 1] + dp[i - 2]

    • 实现

      你其实可以从递推方程看到,我们需要有一个初始值来方便我们计算,起始位置不需要移动 dp[0] = 0,第 1 层楼梯只能从起始位置到达,因此 dp[1] = 1,第 2 层楼梯可以从起始位置和第 1 层楼梯到达,因此 dp[2] = 2,有了这些初始值,后面就可以通过这几个初始值进行递推得到。

    参考代码

    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
    
        int[] dp = new int[n + 1];  // 多开一位,考虑起始位置
    
        dp[0] = 0; dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
    
        return dp[n];
    }
    

     

    三角形最小路径和

    LeetCode 第 120 号问题:三角形最小路径和。

    题目描述

    给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

    例如,给定三角形:

    [
         [2],
        [3,4],
       [6,5,7],
      [4,1,8,3]
    ]
    

    自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

    说明:

    如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

    题目解析

    给定一个三角形数组,需要求出从上到下的最小路径和,也和之前一样,按照四个步骤来分析:

    • 问题拆解:

      这里的总问题是求出最小的路径和,路径是这里的分析重点,路径是由一个个元素组成的,和之前爬楼梯那道题目类似,[i][j] 位置的元素,经过这个元素的路径肯定也会经过 [i - 1][j]或者 [i - 1][j - 1],因此经过一个元素的路径和可以通过这个元素上面的一个或者两个元素的路径和得到。

    • 状态定义

      状态的定义一般会和问题需要求解的答案联系在一起,这里其实有两种方式,一种是考虑路径从上到下,另外一种是考虑路径从下到上,因为元素的值是不变的,所以路径的方向不同也不会影响最后求得的路径和,如果是从上到下,你会发现,在考虑下面元素的时候,起始元素的路径只会从[i - 1][j] 获得,每行当中的最后一个元素的路径只会从 [i - 1][j - 1] 获得,中间二者都可,这样不太好实现,因此这里考虑从下到上的方式,状态的定义就变成了 “最后一行元素到当前元素的最小路径和”,对于 [0][0] 这个元素来说,最后状态表示的就是我们的最终答案。

    • 递推方程

      “状态定义” 中我们已经定义好了状态,递推方程就出来了

      dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
      
    • 实现

      这里初始化时,我们需要将最后一行的元素填入状态数组中,然后就是按照前面分析的策略,从下到上计算即可

    参考代码

    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
    
        int[][] dp = new int[n][n];
    
        List<Integer> lastRow = triangle.get(n - 1);
    
        for (int i = 0; i < n; ++i) {
            dp[n - 1][i] = lastRow.get(i);
        }
    
        for (int i = n - 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];
    }
    

     

    最大子序和

     

    LeetCode 第 53 号问题:最大子序和。

    题目描述

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

    示例:

    输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
    

    进阶:

    如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

    题目解析

    求最大子数组和,非常经典的一道题目,这道题目有很多种不同的做法,而且很多算法思想都可以在这道题目上面体现出来,比如动态规划、贪心、分治,还有一些技巧性的东西,比如前缀和数组,这里还是使用动态规划的思想来解题,套路还是之前的四步骤:

    • 问题拆解:

      问题的核心是子数组,子数组可以看作是一段区间,因此可以由起始点和终止点确定一个子数组,两个点中,我们先确定一个点,然后去找另一个点,比如说,如果我们确定一个子数组的截止元素在 i 这个位置,这个时候我们需要思考的问题是 “以 i 结尾的所有子数组中,和最大的是多少?”,然后我们去试着拆解,这里其实只有两种情况:

         i 这个位置的元素自成一个子数组;

         i 位置的元素的值 + 以 i – 1 结尾的所有子数组中的子数组和最大的值

      你可以看到,我们把第 i 个问题拆成了第 i – 1 个问题,之间的联系也变得清晰

    • 状态定义

      通过上面的分析,其实状态已经有了,dp[i] 就是 “以 i 结尾的所有子数组的最大值

    • 递推方程

      拆解问题的时候也提到了,有两种情况,即当前元素自成一个子数组,另外可以考虑前一个状态的答案,于是就有了

      dp[i] = Math.max(dp[i - 1] + array[i], array[i])
      

      化简一下就成了:

      dp[i] = Math.max(dp[i - 1], 0) + array[i]
      
    • 实现

      题目要求子数组不能为空,因此一开始需要初始化,也就是 dp[0] = array[0],保证最后答案的可靠性,另外我们需要用一个变量记录最后的答案,因为子数组有可能以数组中任意一个元素结尾

    参考代码

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
    
        int n = nums.length;
    
        int[] dp = new int[n];
    
        dp[0] = nums[0];
    
        int result = dp[0];
    
        for (int i = 1; i < n; ++i) {
            dp[i] = Math.max(dp[i - 1], 0) + nums[i];
            result = Math.max(result, dp[i]);
        }
    
        return result;
    }
    

     

    总结

    通过这几个简单的例子,相信你不难发现,解动态规划题目其实就是拆解问题,定义状态的过程,严格说来,动态规划并不是一个具体的算法,而是凌驾于算法之上的一种 思想 。

    这种思想强调的是从局部最优解通过一定的策略推得全局最优解,从子问题的答案一步步推出整个问题的答案,并且利用空间换取时间。从很多算法之中你都可以看到动态规划的影子,所以,还是那句话 技术都是相通的,找到背后的本质思想是关键

    展开全文
  • 动态规划算法的理解

    2019-08-22 22:50:10
    动态规划(dynamic programming)与分治方法类似,都是通过组合子问题解来... 通常按照一下四个步骤来设计一个动态规划算法: 刻画一个最优对结构特征。 递归地定义最优解对值。 计算最优解值,通常采用自...

            动态规划(dynamic programming)与分治方法类似,都是通过组合子问题的解来求解原问题。但是动态规划算法对每个子子问题只求解一次,将其保存在一个表格中,从而无需每次求解一个子子问题时都重复计算,避免来这种不必要对对计算工作。

           通常按照一下四个步骤来设计一个动态规划算法:

    1. 刻画一个最优对结构特征。
    2. 递归地定义最优解对值。
    3. 计算最优解的值,通常采用自底向上的方法。
    4. 利用计算出的信息构造一个最优解。

          动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。首先,需要先找到某个状态的最优解,然后在它的帮助下,找到下一状态的最优解,“状态”用来描述该问题的子问题的解。“状态”并不是随便给的,在大多数情况下,某个状态只与它前面出现的状态有关,而独立于后面的状态。然后分析状态转移方程以及初始状态。

            动态规划的本质就是递归,这样比较容易判断一个问题是否可以用动态规划算法去求解,因为只要思考问题的规模缩小/扩大之后是不是同样的方法求解即可。

         适用应用动态规划算法求解的最优问题应该具备两个要素:

    • 最优子结构
    • 子问题重叠

    如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优解结构的性质。

    重叠子问题其实就是子问题空间必须足够“小”,即问题的递归算法会反复的求解相同的子问题,而不是一直生成新的子问题。

         下面,我们来看一个动态规划经典的问题:求最长递增序列长度LIS(longest increasing subsequence)

    设有由n个不相同的整数组成的数列,记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)

    若存在i1<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie)则称为长度为e的不下降序列

          问题:一个序列有n个数:a[1],a[2],…,a[N],求出最长非降子序列的长度

    首先,我们先理一下思路:

    1)我们最终目标是要求n个数的序列中最长非降子序列的长度,如果能先求出a[1],a[2],a[i](i<N)的最长非降子序列,那么上面的问题变成了原问题的一个子问题,此时问题规模变小了,我们可以让i=1,2,3.......来分析。然后我们定义d(i),表示前i个数中以a[i]结尾的最长非降子序列的长度。这个d(i)就是我们要找的状态。如果我们把d(1)到d(N)都计算出来,那么最终我们要找的答案就是这里面最大的那个。当状态找到了,那么下一步找出状态转移方程。

    2)为了简化理解如何找到状态转移方程的,我们可以让i=1,2,3,4,5。如果我们要求的这n个数的序列是:

    18,7,14,20,18,23

    根据前面的状态,我们可以进行推断:

    (1)i=1时,序列:18,LIS长度d(1)=1;

    (2)i=2时,序列:7,此时7前面没有比7小的了,所以LIS长度d(2)=1;

    (3)i=3时,序列:7,14,此时14前面有7比它小,所以LIS长度d(3)=2也可以理解为d(3)=d(2)+1;

    (4)i=4时,序列:7,14,20,此时20前面7,14比它小,有LIS长度d(4)=3,即d(4)=d(3)+1;

    分析到这里,我们基本上可以找到状态转移的方程了,如果我们已经求出了d(1)到d(i-1),那么d(i)可以用下面的状态转移方程得到:

    d(i) = max{1, d(j) + 1},其中要满足条件:j < i && a[j] <= a[i]

    程序如下:

      public static void getLongest(int[] arr, int n){
        //存放状态
        int[] d = new int[n];
        //最长非降子序列长度初始化为1
        int length = 1;
        //状态初始化为1
        d[0] = 1;
        for (int i = 1; i < n; i++){
          //状态初始化为1
          d[i] = 1;
          for (int j = 0; j < i; j++){
            if (arr[i] > arr[j] && d[j] + 1 > d[i]){
              d[i] = d[j] + 1;
            }
            if (length < d[i]){
              length = d[i];
            }
          }
        }
    
        System.out.println(length);
    
      }

           上面line11-line18即内层for循环其实就是我们在求a[1],a[2],a[i](i<N)的最长非降子序列,此时将问题变成了原问题的一个子问题,此时问题规模变小了,进而在外层for循环求助最后的结果。

           上面的时间复杂度为n^2,下面我们通过二分法将时间复杂度降为nlogn,代码如下:

    public class Test {
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入序列:");
            String[] strLines = scanner.nextLine().trim().split(" ");
            int n = strLines.length;
            int[] nums = new int[n + 1];
            int[] f = new int[n + 1];
            for (int i = 1; i <= n; i++){
                nums[i] = Integer.parseInt(strLines[i-1]);
                f[i] = Integer.MAX_VALUE;
            }
            scanner.close();
            f[1] = nums[1];
            //通过记录f数组的有效位数,求得个数
            int len = 1;
            for (int i = 2; i <= n; i++){
                int l = 0;
                int r = len;
                int mid;
                //若大于末尾,则向后填充
                if (nums[i] > f[len]){
                    f[len++] = nums[i];
                } else {
                    //二分法查找将时间复杂度降为nlogn
                    while (l < r){
                        mid = l + (r-l)/2;
                        if (f[mid] > nums[i]){
                            r = mid;
                        } else {
                            l = mid + 1;
                        }
                    }
                    f[l] = Math.min(nums[i], f[l]);
                }
            }
            System.out.println(len);
        }
    }

    在这我们在继续求解另外一个关于序列的问题,两个序列中的最长公共子序列( LCS )

    譬如给定2个序列:

    1 2 3 4 5

    3 2 1 4 5

    试求出最长的公共子序列。

     显然长度是 3 ,包含 3  4  5三个元素(不唯一)

    解析:

           可以用 dp[i][j] 来表示第一个串的前 i 位,第二个串的前j位的 LCS的长度,那么我们是很容易想到状态转移方程的:

    如果当前的 nums1[i] 和 nums2[j] 相同(即是有新的公共元素) 那么dp[ i ] [ j ] = max(dp[ i ] [ j ], dp[ i-1 ] [ j-1 ] + 1);

    如果不相同,即无法更新公共元素,考虑继承:dp[i][j]=max(dp[i−1][j],dp[i][j−1])

    代码如下:

    public class Test {
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入序列1:");
            String[] str1 = scanner.nextLine().trim().split(" ");
            int n = str1.length;
            int[] nums1 = new int[n+1];
            for (int i = 1; i <= n; i++){
                nums1[i] = Integer.parseInt(str1[i-1]);
            }
            System.out.println("请输入序列2:");
            String[] str2 = scanner.nextLine().trim().split(" ");
            int m = str2.length;
            int[] nums2 = new int[m+1];
            for (int i = 1; i <= m; i++){
                nums2[i] = Integer.parseInt(str2[i-1]);
            }
            scanner.close();
            //dp[i][j]表示两个字符串从头开始,直到第一个串的第i位和第二个串的第j位最多有多少个公共子元素
            int[][] dp = new int[n+1][m+1];
    
            for (int i = 1; i <= n; i++){
                for (int j = 1; j <= m; j++){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    if (nums1[i] == nums2[j]){
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + 1);
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
    }

    下面在看两道题目进行练习巩固。


    一、首先,看一个导弹拦截的问题(http://codevs.cn/problem/1044/

    题目描述 Description

          某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

    输入描述 Input Description

    输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数)

    输出描述 Output Description

    输出这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

    样例输入 Sample Input

    389 207 155 300 299 170 158 65 

    样例输出 Sample Output

    6

    2

    数据范围及提示 Data Size & Hint

    导弹的高度<=30000,导弹个数<=20

    分析:本题其实就是求解最长降序序列长度(每套系统拦截的导弹数量)和最长升序序列长度(系统数量

    代码如下:

    public class Test {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            System.out.println("输入导弹依次飞来的高度(中间用空格间隔): ");
            String[] strs = scan.nextLine().split(" ");
            int[] high = new int[strs.length];
            for (int i = 0; i < strs.length; i++){
                high[i] = Integer.parseInt(strs[i]);
            }
            scan.close();
            //需要的系统数量
            int[] d1 = new int[high.length];
            //每套系统拦截的导弹数量
            int[] d2 = new int[high.length];
            int len1 = 1, len2 = 1;
            d1[0] = 1;
            d2[0] = 1;
            for (int i = 0; i < high.length; i++){
                d1[i] = 1;
                d2[i] = 1;
                for (int j = 0; j < i; j++){
                    //导弹系统数量——最长升序序列长度
                    if (high[i] > high[j] && d1[i] < d1[j] + 1){
                        d1[i] = d1[j] + 1;
                    }
                    if (len1 < d1[i]){
                        len1 = d1[i];
                    }
                    //每套系统拦截的导弹数量——最长降序序列长度
                    if (high[i] <= high[j] && d2[i] < d2[j] + 1){
                        d2[i] = d2[j] + 1;
                    }
                    if (len2 < d2[i]){
                        len2 = d2[i];
                    }
                }
            }
            System.out.println(len2);
            System.out.println(len1);
        }
    }

    二、再看一个数字划分问题(http://codevs.cn/problem/1039/

    题目描述 Description

    将整数n分成k份,且每份不能为空,任意两种划分方案不能相同(不考虑顺序)。
    例如:n=7,k=3,下面三种划分方案被认为是相同的。
    1 1 5

    1 5 1

    5 1 1
    问有多少种不同的分法。

    输入描述 Input Description

    输入:n,k (6<n<=200,2<=k<=6)

    输出描述 Output Description

    输出:一个整数,即不同的分法。

    样例输入 Sample Input

     7 3

    样例输出 Sample Output

    4

    数据范围及提示 Data Size & Hint

     {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}

    分析:

    还是使用动态规划算法,将划分后的数字分成包含1和不包含1两种情况。

    dp[i][j] = dp[i-1][j-1] + dp[i-j][j],

    即:dp[i][j]表示把数字 i 划分为 j 部分;

           dp[i-1][j-1]:划分的j份中至少有一份为1,把这个1拿出来,剩下的相当于把i-1分为j-1份

           dp[i-j][j]:划分的j份中没有一份是1,每一份中都拿走1个1,剩下的相当于把i-j分为j份

           dp状态一般由前一个状态转移而来的。

    代码如下:

    public class DivideNum {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            System.out.println("请输入数字以及划分数目(中间空格隔开):");
            String[] strs = scan.nextLine().split(" ");
            scan.close();
            int n = Integer.parseInt(strs[0]);
            int k = Integer.parseInt(strs[1]);
            int[][] dp = new int[n+1][k+1];
            //初始化dp,先暂时默认成1部分
            for (int i = 0; i < n; i++){
                dp[i][1] = 1;
            }
            //初始化方案数目为1
            int size = 1;
            for (int i = 1; i <= n; i++){
                for (int j = 1; j <=k; j++){
                    if (i >= j){
                        dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
                    }
                    if (size < dp[i][j]){
                        size = dp[i][j];
                    }
                }
            }
            System.out.println(size);
        }
    }

    另外,如果还不太理解的童鞋,可以在在继续看看下面两篇博文:

    展开全文
  • 求两字符串最长公共子序列——程序设计艺术与方法实验 动态规划算法的实现 (1) 求两字符串最长公共子序列。 - 151 - X 一个子序列是相应于 X 下标序列{1, 2, …, m}一个子序列,求解两序列所有子...

    求两个字符串的最长公共子序列——程序设计艺术与方法实验四 动态规划算法的实现

    (1) 求两个字符串的最长公共子序列。 - 151 - X 的一个子序列是相应于 X 下标序列{1, 2, …, m}的一个子序列,求解两个序列的所有子序列中长度最大的,例如输入:pear, peach 输出:pea。
    在这里插入图片描述
    步骤:

    1. 确定子问题
    2. 确定状态转移方程
      res[i][j]表示text1截止到第i个字符串,text2截止到第j个字符串的最长公共子串
      text1[i]=text2[j],res[i][j]=原结果 + 1
      text1[i]!=text2[j],res[i][j]=原结果
      原结果? res[i-1][j],res[i-1][j-1] √,res[i][j-1]
      text1[i] = text2[j],res[i][j] = res[i-1][j-1] + 1
      text1[i] != text2[j],res[i][j] = max{res[i-1][j],res[i][j-1]}
      因此,此题在计算出一个子问题的答案后, 将其存储在一个表中。此后调用将检查表。
      我们先通过状态转移方程填表,并返回表的最右下角元素(最长公共子序列长度)
      之后我们根据递归公式构建了上表,我们将从最后一个元素res[m][n]倒推出text1和text2的LCS。
      如果遇到text 1[i] == text 2[j],记录此时的公共值,此时的值来自于res[i-1][j-1]
      如果遇到text 1[i] != text 2[j] ,此时的值来自于max{res[i-1][j] ,res[i][j-1] }即他两的最大值。
      如果遇到text 1[i] != text 2[j] ,且res[i-1][j] = res[i][j-1] 这种存在分支的情况,这里请都选择一个方向(之后遇到这样的情况,也选择相同的方向)。两种方向都选进行递归。

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    /*
    给定两个字符串text1和text2,返回这两个字符串的最长公共子序列的长度
    一个字符串的子序列是指这样一个新的字符串:
    它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串
    eg. text1 = "abcbcba", text2 = "abcba" 公共子串abcba
    步骤:
    1.确定子问题
    2.确定状态转移方程
    res[i][j]表示text1截止到第i个字符串,text2截止到第j个字符串的最长公共子串
    text1[i]=text2[j],res[i][j]=原结果 + 1
    text1[i]!=text2[j],res[i][j]=原结果
    原结果? res[i-1][j],res[i-1][j-1] √,res[i][j-1]
    text1[i] = text2[j],res[i][j] = res[i-1][j-1] + 1
    text1[i] != text2[j],res[i][j] = max{res[i-1][j],res[i][j-1]}
    */
    string test1;
    string test2;
    vector<vector<int> > res; // 动态规划表
    set<string> lcs;      // set保存所有的LCS
    int lcs_length(int m, int n){
    	// 表的大小为(m+1)*(n+1)
    	res = vector<vector<int> >(m + 1, vector<int>(n + 1));
    	for (int i = 0; i < m + 1; ++i){
    		for (int j = 0; j < n + 1; ++j){
    			// 第一行和第一列置0
    			if (i == 0 || j == 0)
    				res[i][j] = 0;
    			else if (test1[i - 1] == test2[j - 1])
    				res[i][j] = res[i - 1][j - 1] + 1;
    			else
    				res[i][j] = max(res[i - 1][j], res[i][j - 1]);
    		}
    	}
    	return res[m][n];
    }
    void lcs_print(int i, int j, string lcs_str){
    	while (i > 0 && j > 0){
    		if (test1[i - 1] == test2[j - 1]){
    			lcs_str.push_back(test1[i - 1]);
    			i--;
    			j--;
    		}
    		else{
    			if (res[i - 1][j] > res[i][j - 1])
    				i--;
    			else if (res[i - 1][j] < res[i][j - 1])
    				j--;
    			else{
    				lcs_print(i - 1, j, lcs_str);
    				lcs_print(i, j - 1, lcs_str);
    				return;
    			}
    		}
    	}
    	reverse(lcs_str.begin(), lcs_str.end());
    	lcs.insert(lcs_str);
    }
    int main(){
    	while(cin >> test1){
    		cin>> test2;
    		int m = test1.length();
    		int n = test2.length();
    		int length = lcs_length(m, n);
    		cout << "最长公共子串的长度是:" << length << endl;
    		string str;
    		lcs_print(m, n, str);
    		set<string>::iterator it = lcs.begin();
    		cout << "最长公共子串是:"<<endl ;
    		for (; it != lcs.end(); it++)
    			cout << *it << endl;
    		lcs.clear();
    		res.clear();
    	}
    	return 0;
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • 动态规划算法

    2011-11-21 22:39:01
    动态规划的基本思想其实就是分治,但是与分治算法还是有区别的,动态规划划分的规模小的问题不是相互独立的。整个问题的最优解是建立在子问题的基础上的。 用动态规划方法求解问题一般分为以下四个步骤: 1、观察...
  • 动态规划和贪心算法

    2019-11-03 18:29:31
    动态规划 动态规划:通过组合子问题的解来求解原问题,常用来求解最优化问题。常用来解决以下几类问题,但不是说遇到类似问题必须用动态规划来解决,可以往这方面去想: ...动态规划问题的四个解决步骤:...
  • 动态规划算法笔记

    2015-04-01 12:38:09
     一般有如下四个步骤:  刻画一个最优解的结构特征。递归地定义最优解的值。计算最优解的值,通常采用自底向上的方法。利用计算出的信息构造一个最优解。 动态规划的一些特征 记忆化...
  • 点击关注上方“五分钟学算法”,设为“置顶或星标”,第一时间送达干货。转自面向大象编程本期例题:LeetCode 198. House Robber 打家劫舍(Easy)你是一专业小偷...
  • 但是,来看一组数据 个人过桥花费时间分别为 1 2 5 10,按照贪心算法答案是19,但是实际答案应该是17。 具体步骤是这样: 第一步:1和2过去,花费时间2,然后1回来(花费时间1); 第二歩:3和4过去...
  • 算法导论-动态规划

    千次阅读 2018-10-07 16:06:51
    通常动态规划可以按照如下四个步骤进行设计: 1.刻画一个最优解结构特征; 2.递归地定义最优解值; 3.计算最优解值,通常采用自底向上方法; 4.利用计算出信息构造一个最优解(按照要求,可有可无)。...
  • 算法设计_动态规划

    2016-02-05 12:20:01
    动态规划算法设计的四个步骤: 1.刻画一个最优解的结构特征。 2.递归地定义最优解的值。 3.计算最优解的值通常采用自底向上的方法。 4.利用计算出的信息构造一个最优解。 典型问题 1.钢条切割问题 给定...
  • 动态规划 步骤 描述最优解结构 递归以求最优解值 自底向上计算最优解 由计算结果构造最优解 装配线调度 最快路线结构 一问题额最优解包含了子问题最优解:即最优子结构 递归解 矩阵链乘 ...
  • 算法复习之动态规划

    2020-06-24 15:43:05
    前言 算法真难!我现在只想及格,千万别让我挂了 动态规划原理 ...我自己认为这是动态规划最大特点了,以空间换时间 自底向上计算 整体问题解取决于子问题解 与递归分治区别 将结果存入表中
  • 动态规划算法求解0,1背包问题

    千次阅读 2015-05-11 21:14:05
    看看动态规划的四个步骤:对于动态规划算法,我们必须明确两个基本要素,这两个要素对于在设计求解具体问题的算法时,是否选择动态规划算法具有指导意义:
  • 文章目录一、概述——递归、分治与动态规划1、递归2、分治3、动态规划二、动态规划1、基本概念2、动态规划解决问题的四个步骤案例一——爬台阶问题简单递归:动态规划(一):动态规划(二)案例二——三角形最小...
  • 目录动态规划与字符串编辑距离动态规划基本思想四个步骤三个例子 动态规划与字符串编辑距离 动态规划 动态规划(dynamic programming)是解决多阶段决策问题常用最优化理论,该理论由美国数学家Bellman等人...
  • 动态规划应用于子问题重叠情况,即不同子问题具有公共子子问题。...四个步骤来设计一个动态规划算法 1.刻画一个最优解结构特征(寻找最优子结构,然后利用这种子结构从子问题最优解构造出原问题最优...
  • 算法分析--动态规划

    2021-01-04 21:15:46
    一、动态规划的基本思想:求解问题分为多阶段或多个子问题,然后按顺序求解各个问题,最后一子问题就是初始问题的解。 动态规划=贪婪策略+递推+存储递推结果 空间换取时间 二、主要概念 阶段:把问题分为几...
  • 把常用的算法在好好总结学习一下,翻了翻去年博文还是用c写,拿出来扩充一下。 目录 动态规划 原理 ...2、字符串编辑距离 ...动态规划 ...将原问题分成规模更小子问题,...一般有四个步骤:定义最优子问题->...
  • 动态规划与分治方法相似,都是通过组合子问题解来求解原问题 分治方法 将问题划分为互不相交子问题,递归地求解子问题,再将所有解组合起来 动态规划 应用于子问题重叠情况,即不同子问题具有公共子...
  • 动态规划常用来解决最优化问题,在这类问题中,我们通过做出一组选择来达到最优解。...我们通常按照如下四个步骤来设计一个动态规划算法: 1.刻画一个最优解结构特征。 2.递归定义最优解值。
  • 动态规划的四个步骤: 1)描述最优解的结构; 2)递归定义最优解的值; 3)按自低向上的方式计算最优解的值(首先找到子问题的最优解,解决子问题,最后找到问题的一个最优解); 4)由计算出的结果构造一个最优...
  • 今天看完了算法导论动态规划的一些简单介绍以及关于装配线调度的系列的问题,真心的感觉算法这玩意好虐,但是真心的有趣,废话不说,切入正题。  书上说的动态规划是分四个步骤进行求解,抄抄:描述最优解结构,...
  • 算法分析与设计之动态规划“二”、“三”、“四” 两个关键成分: 1.最佳子结构; 2.重叠子问题。 三个基本组成部分: 1.递推关系; 2.表格计算; 3.回溯过程。 四个步骤: 1.表征最优解结构; 2.递归定义最优...
  • 动态规划算法思想简介: 将一个问题分解为多个子问题,这点和分治法类似,但是每个子...一般地,动态规划思想一般用来解最优化问题,主要分为以下四个步骤: (1)找出最优解性质,并刻画其结构特征; (2)...
  • 我们通常按照下面四个步骤来设置动态规划算法: 刻画一个最优解结构特征 递归地定义最优解值 计算最优解值,通常采用自底向上方法 利用计算出信息构造一个最优解 前三步是动态规划算法
  • 本章介绍了设计和分析高效算法的三种重要技术之一的动态规划,书中列举了四个常见问题,分析如何采用动态规划方法进行解决。 基本概念 动态规划通常应用于最优化问题,此类问题可能包含多个可行解。每个解有一个值,...
  • 算法导论一书部分—高级设计和分析...动态规划算法的设计可以分为如下4个步骤: 描述最优解结构 递归定义最优解值 按照自底向上方式计算最优解值 由计算出结果构造一最优解 15.1 装配线调
  • 并且动态规划这种通过空间换取时间的算法思想在实际工作中也会被频繁用到,这篇文章目的主要是解释清楚什么是动态规划,还有就是面对一道动态规划问题,一般思考步骤以及其中注意事项等等,最后通过几道题目...
  • 动态规划(Dynamic Programming,DP)一、概念二、思想或策略三、步骤四、DP适用情况五、C++实现DP一般模板六、C++实现LeetCode动态规划相关例题6.1 Leetcode5–最长回文子串6.2 Leetcode72–编辑距离七、总结 ...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 140
精华内容 56
关键字:

动态规划的四个算法步骤