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

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

     

    什么是动态规划

    如果你还没有听说过动态规划,或者仅仅只有耳闻,或许你可以看看 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;
    }
    

     

    总结

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

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

    展开全文
  • 文章目录一、概述——递归、分治与动态规划1、递归2、分治3、动态规划二、动态规划1、基本概念2、动态规划解决问题的四个步骤案例一——爬台阶问题简单递归:动态规划(一):动态规划(二)案例二——三角形最小...

    一、概述——递归、分治与动态规划

    1、递归

    递归是一种直接或者间接调用自身函数或者方法的算法。

    通俗来说,递归的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。它有如下特点:

    • 一个问题可以分解为若干子问题进行求解;
    • 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样;
    • 有一个明确的递归结束条件,即规模很小时能够直接得到问题的解。

    2、分治

    分治法求解问题可分为两大步:

    • 分(Divide):将原问题分解为若干个规模较小但类似于原问题的子问题进行求解;
    • 治(Conquer):合并这些子问题的解来建立原问题的解。

    3、动态规划

    动态规划和分治法类似,也是将原问题分解为若干个规模较小的子问题进行求解,然后合并子问题的解得到原问题的解。区别在于这些子问题可能会有重叠,一个子问题在求解后,可能会再次求解,于是我们想到将这些子问题的解存储起来,当下次再次求解这个子问题时,直接拿过来用。因而省掉很多重复运算,得到更小的运行时间。

    因此,分治法一般用来解决子问题相互对立的问题,称为标准分治,而动态规划用来解决子问题重叠的问题。

    二、动态规划

    1、应用动态规划求解的问题的四个特点

    如果题目是求一个问题的最优解(最大值或者最小值),而且该问题能够分解为若干个子问题,并且子问题之间还有重叠的更小的子问题,就可以考虑用动态规划来解决这个问题。

    可以应用 动态规划 求解的问题的四个特点:

    • 我们要求解的是一个问题的最优解(最大值或者最小值);
    • 整体问题可以分解成若干子问题,并且整体问题的最优解依赖于各个子问题的最优解;
    • 这些小问题之间存在相互重叠的更小的子问题;
    • 为避免重复求解子问题,我们把小问题的解存储下来,以此为基础求解大问题的解。即从上往下分析问题,从下往上求解问题。

    我们以面试题 14. 剪绳子为例,来看看动态规划分析问题的过程。题目的要求是,如何把长度为 nn 的绳子剪成若干段,使得得到的各段长度的乘积最大。

    问题的目标是求剪出的各段绳子长度的乘积最大值,也就是求一个问题的最优解

    我们定义函数 f(n)f(n) 表示把长度为 nn 的绳子剪成若干段后得到的乘积的最大值。假设我们第一刀剪在长度为 i(0<i<n)i(0 < i<n) 的位置,得到长度为 iinin - i 的两段。要得到 f(n)f(n),那么就要把 iinin - i 也分别剪成若干段,使得它们各自剪出的每段绳子的长度乘积最大。也就是说,整体问题的最优解依赖于各个子问题的最优解

    我们假设 n=10n = 10,第一次把绳子剪成 4 和 6 的两段,即 f(4)f(4)f(6)f(6)f(10)f(10) 的子问题。接下来,我们把 4 剪成两个 2,即 f(2)f(2)f(4)f(4) 的子问题;把 6 剪成 2 和 4 的两段,即 f(2)f(2)f(4)f(4)f(6)f(6) 的子问题。我们注意到, f(2)f(2)f(4)f(4)f(6)f(6) 重叠的更小的子问题。也就是说,我们把大问题分解为若干个小问题,这些小问题之间存在相互重叠的更小的子问题

    为了避免重复求解子问题,我们用从下往上的顺序先计算小问题的最优解并存储下来(一般存储在一维或者二维数组里),再以此为基础求取大问题的最优解。也就是,从上往下分析问题,从下往上求解问题

    在应用动态规划的时候,我们每一步都可能面临若干个选择。比如剪绳子,我们在剪第一刀的时候就有 n1n - 1 个选择,我们可以剪在长度为 1,2,...,n11, 2, ... , n - 1 的任意位置。但事先我们不知道哪个是最优的,所以只好把所有的可能都尝试一遍,然后比较得出最优解。用公式表示就是 f(n)=max(f(i)×f(ni))f(n) = max(f(i) \times f(n - i)),其中 0<i<n0 < i < n。这个过程其实就是建立大问题和小问题之间具体联系的过程,并用数学公式表示出来,即状态转移方程

    2、“三步走” 解决动态规划问题

    • 明确目标,定义状态: 明确我们要求的目标是什么。比如在剪绳子问题中,我们把 f(n)f(n) 定义为 “把长度为 nn 的绳子剪成若干段后得到的乘积的最大值”。
    • 问题拆解,推导状态转移方程: 把大问题分解成小问题,并用递推公式表示出大问题和小问题之间的具体关系。比如,剪绳子问题中,找到 f(n)=max(f(i)×f(ni))f(n) = max(f(i) \times f(n - i)),其中 0<i<n0 < i < n
    • 寻找边界条件: 我们得到的状态转移方程是一个递推式,需要找到递推的终止条件。比如,剪绳子问题中,若 n=2n = 2,只能剪成长度为 1 的两段,所以有 f(2)=1f(2) = 1;若 n=3n = 3,可以剪成长度为 1 和 2 的两段或者长度为 1 的三段,又 1×2>1×1×11 \times 2 > 1 \times 1 \times 1,所以有 f(3)=2f(3) = 2。据此,我们可以得到 f(4)f(4)f(5)f(5),直到 f(n)f(n)

    三、案例

    案例一——剪绳子

    思路:

    • 明确目标,定义状态: 我们要求的是“把长度为 nn 的绳子剪成若干段后得到的乘积的最大值”,因此,我们定义 f(i)f(i) 表示 “把长度为 ii 的绳子剪成若干段后各段长度乘积的最大值”。
    • 问题拆解,推导状态转移方程: 长度为 ii 的绳子,我们在剪第一刀的时候有 i1i - 1 个选择,我们可以剪在长度为 1,2,...,i11, 2, ... , i - 1 的任意位置,从中找出乘积最大的剪法,即 f(i)=max(f(j)×f(ij)),0<j<if(i) = max(f(j) \times f(i - j)),0 < j < i
    • 寻找边界条件: 我们得到的状态转移方程是一个递推式,需要找到递推的终止条件。比如,若 n=2n = 2,只能剪成长度为 1 的两段,所以有 f(2)=1f(2) = 1;若 n=3n = 3,可以剪成长度为 1 和 2 的两段或者长度为 1 的三段,又 1×2>1×1×11 \times 2 > 1 \times 1 \times 1,所以有 f(3)=2f(3) = 2。据此,我们可以得到 f(4)f(4)f(5)f(5),直到 f(n)f(n)

    参考代码:

    class Solution {
        public int cuttingRope(int n) {
            if(n < 2)
                return 0;
            if(n == 2)
                return 1;
            if(n == 3)
                return 2;
            int[] product = new int[n + 1];
            product[1] = 1;
            product[2] = 2;
            product[3] = 3;
            int maxProduct = 0;
            for(int i = 4; i <= n; i++){
                for(int j = 1; j <= i / 2; j++){
                    maxProduct = Math.max(maxProduct, product[j] * product[i - j]);
                }
                product[i] = maxProduct;
            }
            return product[n];
        }
    }
    

    案例二——爬台阶问题

    题目描述:

    一个人爬楼梯,每次只能爬 1 个或 2 个台阶,假设有 n 个台阶,那么这个人有多少种不同的爬楼梯方法?

    动态规划(一):

    • 明确目标,定义状态: 我们要求的是爬上 n 个台阶有多少种爬法。所以,我们可以定义 dp[i] 表示 “爬上 i 个台阶的爬法”。
    • 问题拆解,推导状态转移方程: 由于每次只能爬 1 个或 2 个台阶,所以到达第 n 个台阶可以从第 n - 1 个台阶或者第 n - 2 个台阶到达,因此得到递推方程:dp[i]=dp[i1]+dp[i2]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 <= 2)
            return n;
        // 创建数组,保存状态信息
        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];
    }
    

    递归:

    我们也可以使用递归来解决这个问题。由于每次只能爬 1 个或 2 个台阶,根据第一步的走法把所有走法分为两类:

    • 第一步爬了 1 个台阶;
    • 第一步爬了 2 个台阶;

    所以 n 个台阶的走法就等于先爬 1 阶后,剩余 n-1 个台阶的走法 ,然后加上先爬 2 阶后,剩余 n-2 个台阶的走法,得到递推公式:
    f(n)=f(n1)+f(n2)f(n) = f(n-1)+f(n-2) 递归结束条件:

    • 当 n = 1 时,f(1) = 1;
    • 当 n = 2 时,f(2) = 2。

    参考代码:

    int f(int n) {
    	if (n <= 2) 
      		return n;
    	return f(n-1) + f(n-2);
    }
    

    动态规划(二):

    上面的递归方法是自顶而下的进行运算,也就是先算 f(n),再算f(n - 1)、f(n-2) … …但是,计算 f(n) 时,f(n)=f(n1)+f(n2)f(n) = f(n-1)+f(n-2);计算 f(n-1) 时,f(n1)=f(n2)+f(n3)f(n - 1) = f(n-2)+f(n-3),又要计算一次 f(n-2)。所以整个的递归过程中存在许多重复计算。这种方法的时间复杂度为 O(2n)O(2^n)

    动态规划是从下往上求解问题的过程,即:

    • 当 n = 1 时,f(1) = 1;
    • 当 n = 2 时,f(2) = 2;
    • 当 n = 3 时,f(3) = f(2) + f(1) = 3;
    • 当 n = 4 时,f(4) = f(3) + f(2) = 5;
      … …

    可以看出,在每一次迭代过程中,只需要知道之前的两个状态,就可以推导出新的状态。所以,我们可以对第一种动态规划进行优化,计算每个状态时,只保存它的前两个状态并不断更新,而不用记录所有的状态。

    参考代码:

    int f(int n) {
        if (n <= 2) 
      		return n;
        // a 保存第 i-2 个状态的数据,b 保存第 i-1 个状态的数据, 
        int a = 1, b = 2;
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = a + b;// temp 保存当前状态的数据
            a = b;
            b = temp; 
        }
        return temp; 
    }
    

    优化后的代码,时间复杂度降为 O(n)。

    案例三——三角形最小路径和

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

    题目描述:

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

    例如,给定三角形:

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

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

    说明:

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

    思路:

    我们的目标是找出自顶向下的最小路径和。如果没有好的着手点,就先分析几种简单的情况:

    • 如果三角形只有两层,如

         [2],
        [3,4]
      

      我们找到最后一层的最小值,再加上第一层的数,就是最小路径和,即 2 + 3 = 5。

    • 如果三角形有三层,如

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

      我们先找左下角 3、6、5 的最小路径和 3 + 5 = 8,再找右下角 4、5、7 的最小路径和 4 + 5 = 9,两者的最小值再加上第一层的数就是整个三角形的最小路径和,即 2 + 8 = 10。

    可以看出,分析三层三角形的过程,是从下往上进行计算的,我们也可以用这个思路分析层数更多的三角形。也就是,从最底下的一层逐层向上计算,计算至顶层时,就得到了整个三角形的最小路径和。

    因此,我们定义状态dp[i][j]dp[i][j] 表示“从三角形的最底层到当前位置的最小路径和”。由于每一步只能移动到下一行中相邻的节点上,所以,当前位置的最小路径和就是它的下一行的两个相邻节点最小路径和的最小值加上当前位置的数字,可得到递推方程
    dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j] 数组初始化: 我们采用自下而上的策略,首先考虑的是最底下一行的元素,最底下一行的元素就表示它们到倒数第二行元素的路径。因此直接将最后一行的元素填入状态数组中,然后从下往上计算。

    参考代码:

    class Solution {
        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> curRow = 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]) + curRow.get(j);
                }
            }
            return dp[0][0];
        }
    }
    

    更多案例:

    leetcode 刷题(87)——64. 最小路径和
    leetcode 刷题(88)——53. 最大子序和
    leetcode 刷题(89)——221. 最大正方形

    展开全文
  • 解决动态规划问题通常采用四个步骤: 问题拆解(找到问题的子问题) 状态定义(使当前状态就是当前问题的解) 写出递推方程(之前相邻子问题的答案推出当前状态的答案) 代码实现 通过几个题目去理解动态规划和...

    动态规划不是一个具体的算法,而是一种思想。

    这种思想具体的就是 从局部最优解采用一定策略推导出全局最优解,从子问题的答案中一步步推出整个问题的答案。

    解决动态规划问题通常采用四个步骤:

    1. 问题拆解(找到问题的子问题)
    2. 状态定义(使当前状态就是当前问题的解)
    3. 写出递推方程(之前相邻子问题的答案推出当前状态的答案)
    4. 代码实现

    通过几个题目去理解动态规划和这四个步骤。

    • 三角形最小路径和问题

    问题描述

    给定一个三角形,找出自顶向下的最小路径和.每一步只能移动到下一行中相邻的节点上:
    [        
          [2]
         [3,4]
        [6,5,7]
       [4,1,8,3]
    ]
    自顶向下的最小路径和为 11 (即,2+3+5+1=11)
    
    #说明如果你可以用O(n)的额外空间(n为三角形的总行数)来解决问题,那么你的算法会很加分.
    #(这个是降低空寂复杂度的问题,实现算法之后在考虑改善算法,先不考虑他)

    按照上面四步分析问题:

    首先问题的拆解:
    其实这个三角形可以看出来就是一个二维数组
    这里的问题是求最小路径和,所有路径是由一个个元素(数字)组成的
    所以问题就可以想象成:
    每到达一个元素的路径是由当前元素加上当前元素的上一个或两个元素路径得到的
    进而把问题拆解成到达每一个元素最小路径的子问题
    
    状态定义:
    
    状态定义就是要和问题求解的答案紧密联系到一起
    这个问题有两个思路,一个是从上到下找路径,另一个从下到上找路径
    
    首先我们看从上到下怎么想:
    
    这里会有一个问题,看下面例子:
    [        
          [2]
         [3,4]
        [6,5,1]
       [4,1,8,3]
    ]
    
    显然最短路径是 2 + 4 + 1 + 3 = 10
    如果只考虑当前从2到3是最短,不选择4,当到下一层时
    根据问题要求(每一步只能移动到下一行中相邻的节点上)就不能选择1,问题答案就错了。
    
    还有一个问题:
    
    每一层元素的起始元素路径只能选择[i-1][j]即上一层的起始元素
    最后元素选[i-1][j-1],即上一层最后一个元素
    但是中间元素就有[i-1][j],[i-1][j-1]两种选择
    所以就不太好实现。我们用从下到上的思想。
    
    从下到上的方式:
    
    [        
          [2]         [10]  #我们可以看出[0][0]个元素就是我们的答案
         [3,4]       [9 8]
        [6,5,1]     [7 6 4] # 6可以选4和1,5可以选1和8  #记录当前所有元素
       [4,1,8,3]    从最后一层向上递推                  #到最后一层最短路径
    ]
    
    我们定义的状态就是 最后一行元素到当前所有元素最小路径和。
    
    
    递推方程:
    
    状态定义好了,递推方程就好写了 
    第[i][j]个元素为当前状态 = 三角形第[i][j]个元素加上([i+1][j]与[i+1][j+1]中小的)
    
    dp[i][j] = triangle[i][j]+min(dp[i+1][j],dp[i+1][j+1])
    
    代码实现:
    
    在文末.
    • 数组中连续子数组的最大和

    问题描述:

    给定一个整数数组N,找到一个具有最大和的连续子数组
    (子数组最少包含一个元素),返回其最大和。
    
    例如:
    
    输入:[1,-5,2,4,-1,3]
    输出:8
    
    因为连续子数组[2,4,-1,3]的和最大。

    按照四步分析问题:

    1.拆解问题
    
    要找整个数组中最大的子数组和,就是去比较所有子数组谁
    的和最大.
    子数组可以看成一个区间,都会有一个起点和一个终点定义.
    由一个起点到第 i 个点组成的子数组 换句话说就是:
    以第i个数结尾的子数组,我们去求解所有以第i个数为结尾的
    子数组的最大和.
    例如:
    [1,2,11,2,3]
              ^
              |
             第i个数是3,则以3结尾的最大和就是前第i-1为结尾,
    此处是以2结尾的子数组[1,2,-1,2]的最大和加上第i个数,也就是3.
    
    [1,2,11,2,3]
       ^
       |
       第i个数是2,则以2结尾的最大和就是前第i-1为结尾,
    此处是以1结尾的子数组[1]的最大和加上第i个数,也就是2.
    
    这样我们就可以把问题从i 拆解成 i-1 即:
    从第一个起始元素开始推出第 i 个……直到整个数组结束。
    
    如果i-1结尾子数组的最大和为负数,则i结尾字数组最大和就是i.
    
    2.状态定义
    
    定义状态应该紧密联系我们最终想要的答案,这个问题第i个状态
    dp[i] 就是以i为结尾的所有子数组最大和.
    
    3.递推方程
    
    dp[i] = max(dp[i-1],0) + array[i]
    
    4 代码实现
    
     文末

    问题描述:

    一共有 n 阶楼梯,每一次你可以爬一个台阶或两个
    你有多少种不同的方法可以爬到楼顶?
    (其中,给定的 n 是一个整数)
    
    示例:
    
    输入:2
    输出:2
    
    因为两阶台阶有两种方式爬到楼顶
    1. 爬一阶再爬一阶
    2. 直接爬两阶

    按照四步分析问题:

    1.拆解问题
    
    一共n阶台阶,有两种方式爬,所以我们到达第n阶的时候
    不是从第n-2爬上来,就是从第n-1阶爬上来,所以我们把
    问题看成到达第 n-2 阶时所有方式加上到达第n-1阶时
    所有方式就是到达第n阶的所有方式.
    
    2.状态定义
    
    第 i 个状态dp[i]就是到达第 i 阶楼梯时存在的所有爬楼
    梯方法种类数量.
    
    3.递推方程
    
    dp[i] = dp[i-1] + dp[i-2] 
    
    4.代码实现
     
        文末

     

    '''
    
    三角形最小路径和(动态规划问题)
    
    '''
    
    class Solution(object):
        def minimumTotal(self, triangle):###原始算法
            if not triangle:
                return 0
            n=len(triangle)
            dp=[[None]*n]*n
            array = triangle[-1]
    
            for i in range(0,n):
                dp[n-1][i] = array[i]
    
            for i in range(n-2,-1,-1):
                for j in range(0,len(triangle[i])):
                    dp[i][j] = min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
            
            return dp[0][0]
            
        def minimumTotal_test(self, triangle):#####改进算法
            if not triangle:
                return 0
            h = len(triangle)  # 金字塔高度
            lay = triangle[-1]  # 取到金子塔最下面一层:是一个列表
            i = h - 2   # 取到金字塔层数的倒数第二层: 是一个数字
            while i >= 0:
                j = 0  # j:遍历金字塔每一层中元素指针
                while j <= i:  # 本来行数和每层的元素数量是一致的,但索引从0开始所以减1,底下j有j+1所以再次减1,故直接是j<=i
                    lay[j] = min(lay[j], lay[j + 1]) + triangle[i][j]  # 对上一层的一个值找其正下方和左下方的最小值,赋到其上
                    j += 1
                i -= 1
            return lay[0]  # i为0时取到的是最上面一层,最上面一层只有一个值 
            
    if __name__ == '__main__':
        s=Solution()
        print(s.minimumTotal_test([[2],[2,3]]))   
    
    
    '''
    输入一个整形数组,可能有正有负,求数组中连续子数组的最大和
    要求时间复杂度为O(n)
    '''
    
    class Solution:
        def multiply(self , A):
            
            n=len(A)
            dp=[None]*n
            dp[0]=A[0] #初始化,数组起始元素,最大和是元素本身
            result=0
            for i in range(1,n):
                dp[i]=max(dp[i-1],0)+A[i]
                result = max(result,dp[i])
            return result
    
    if __name__ == '__main__':
        s=Solution()
        #输入以逗号分隔的数组元素
        str_in= input()
        a = [int(n) for n in str_in.split(',')] #将输入转变成数组
        print(s.multiply(a))  
    
    '''
    爬楼梯问题
    '''
    
    class Solution:
        def  Stairs(self , n):
            dp=[None]*n
            dp[0] = 1 #初始化第一个台阶
            dp[1] = 2
            
            for i in range(2,n):
                dp[i] = dp[i-1] + dp[i-2]
            return dp[n-1]
            
    if __name__ == '__main__':
        s=Solution()
        print(s.Stairs(4))  

     

    参考文章

     

    展开全文
  • 动态规划

    2020-08-26 20:05:50
    动态规划的基本思想 将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。...设计动态规划法的步骤 1.找出最

    动态规划的基本思想

    将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

    适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。

    如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。
    我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。

    设计动态规划法的步骤

    1.找出最优解的性质,并刻画其结构特征;
    2. 递归地定义最优值(写出动态规划方程);
    3. 以自底向上的方式计算出最优值;
    4.根据计算最优值时得到的信息,构造一个最优解。
    步骤1~3是动态规划算法的基本步骤。 在只需要求出最优值的情形,步骤4可以省略;
    若需要求出问题的一个最优解,则必须执行步骤4。

    动态规划问题的特征

    最优子结构:
    当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。

    重叠子问题:
    在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。

    EQ1
    矩阵连乘积问题。

    m×n矩阵A与n×p矩阵B相乘需耗费 的时间。 我们把mnp作为两个矩阵相乘所需时间的测量值。
    现在假定要计算三个矩阵A、B和C的乘积,有两种方式计算此乘积。
    1.先用A乘以B得到矩阵D,然后D乘以C得到最终结果,这种乘法的顺序为(AB)C;
    2. 乘法的顺序为A(BC)。
    尽管这两种不同的计算顺序所得的结果相同,但时间消耗会有很大的差距。

    动态规划
    #define NUM 51
    int p[NUM];
    int m[NUM][NUM];
    int s[NUM][NUM];
    void MatrixChain (int n)
    {
      for (int i=1;  i<=n;  i++) m[i][i] = 0;
      for (int r=2;  r<=n;  r++)
    	for (int i=1;  i<=n-r+1;  i++) 
    	{
    	  int j=i+r-1; 
    	  //计算初值,从i处断开
    	  m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
    	  s[i][j] = i; 
    	  for (int k=i+1;  k<j;  k++) 
    	  { 
    		int t = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
    		if (t < m[i][j]) {m[i][j] = t; s[i][j] = k;}
    	  }
    	}
    }
    
    递归算法
    int Recurve(int i, int j)
    {
      if (i == j) return 0;
      int u = Recurve(i, i)+Recurve(i+1,j)+p[i-1]*p[i]*p[j];
      s[i][j] = i;
      for (int k = i+1; k<j; k++) 
      {
    	int t = Recurve(i, k) + Recurve(k+1,j)+p[i-1]*p[k]*p[j];
    	if (t<u) { u = t; s[i][j] = k;}
      }
      m[i][j] = u;
      return u;
    }
    
    备忘录算法
    
    int LookupChai  (int i, int j)
    {
      if (m[i][j]>0) return m[i][j];
      if (i==j) return 0;
      int u = LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];
      s[i][j] = i;
      for (int k = i+1; k<j; k++) 
      {
    	int t = LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];
    	if (t < u) { u = t; s[i][j] = k;}
      }
      m[i][j] = u;
      return u;
    }
    

    EQ2
    计算最大子段和问题–动态规划。

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int dp[200005],a[200005];
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        dp[1]=a[1];
        int sta=1,en=1;
        int ans=a[1];
        for(int i=2;i<=n;i++)
        {
            dp[i]=max(dp[i-1]+a[i],a[i]);
            if(dp[i-1]<0)
              sta=i;
            if(ans<dp[i])
              en=i;
            ans=max(ans,dp[i]);
        }
        printf("%d %d\n",sta,en);
        printf("%d\n",ans);
        return 0;
    }
    

    EQ3
    0-1背包问题–动态规划。

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include<cmath>
    #include<algorithm>
    #define max(a,b) a>b?a:b
    using namespace std;
    int main()
    {
        int T,N,V,f[1001],vol[1001],val[1001],tem;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d %d",&N,&V);
            for(int i=1;i<=N;i++)
            scanf("%d",&val[i]);
            for(int i=1;i<=N;i++)
            scanf("%d",&vol[i]);
            memset(f,0,sizeof(f));
            for(int i=1;i<=N;i++)
            {
                for(int j=V;j>=vol[i];j--)
                {
                   f[j]=max(f[j],f[j-vol[i]]+val[i]);
                }
            }
            cout<<f[V]<<endl;
        }
        return 0;
    }
    

    EQ4
    最长公共子序列。

    #define NUM 100
    int c[NUM][NUM];
    int b[NUM][NUM];
    void LCSLength (int m, int n, const char x[],char y[])
    {  
      int i,j;
      //数组c的第0行、第0列置0
      for (i = 1; i <= m; i++) c[i][0] = 0;
      for (i = 1; i <= n; i++) c[0][i] = 0;
      //根据递推公式构造数组c
      for (i = 1; i <= m; i++)
      for (j = 1; j <= n; j++)
      {
    	if (x[i]==y[j]) 
    	  {c[i][j]=c[i-1][j-1]+1; b[i][j]=1; }		
    	else if (c[i-1][j]>=c[i][j-1]) 
    		{c[i][j]=c[i-1][j]; b[i][j]=2; }	
    	else { c[i][j]=c[i][j-1]; b[i][j]=3; }		
      }
    }
    ……
    void LCSLength (int m, int n, const char x[],char y[])
    {  
      int i,j;
      //数组c的第0行、第0列置0
      ……;
      //根据递推公式构造数组c
      
       for (i = 1; i <= m; i++)
      for (j = 1; j <= n; j++)
      {
    	if (x[i]==y[j]) 
    	  {c[i][j]=c[i-1][j-1]+1; b[i][j]=1; }		
    	else if (c[i-1][j]>=c[i][j-1] ) 
    		{c[i][j]=c[i-1][j]; b[i][j]=2; }		
    	else { c[i][j]=c[i][j-1]; b[i][j]=3; }		
      }
    }
    void LCS(int i,int j,char x[])
    {
    	if (i ==0 || j==0) return;
    	if (b[i][j]== 1){ LCS(i-1,j-1,x);  printf("%c",x[i]); }
    	else if (b[i][j]== 2) LCS(i-1,j,x);
    	else LCS(i,j-1,x);
    }
    
    展开全文
  • 动态规划

    2019-10-28 20:54:10
    文章目录一、 什么是动态规划二、动态规划的基本思想三、动态规划的问题特征、设计动态规划的步骤五、最长公共子序列六、0-1背包问题(不能分割) 一、 什么是动态规划 动态规划(Dynamic Programming)是运筹学...
  • 状态转移方程 动态规划中当前状态往往依赖于前一阶段状态和前一阶段决策结果。...在前面文章《动态规划-开篇》讲到了如何设计一个动态规划算法,有以下四个步骤: 1、刻画一个最优解结构特征。 2...
  • 动态规划中当前状态往往依赖于前一阶段状态和前一阶段决策结果。例如我们知道了第i个阶段状态Si以及决策Ui,那么第i+1...在前面文章《动态规划-开篇》讲到了如何设计一个动态规划算法,有以下四个步骤: 1
  • 一般解决动态规划问题,分为四个步骤,分别是 问题拆解,找到问题之间具体联系 状态定义 递推方程推导 实现 “1+1+1+1+1+1+1+1” 得出答案是 8,那么如何快速计算 “1+ 1+1+1+1+1+1+1+1”,我们首先可以对这个...
  • 动态规划求解编辑距离问题 ... 补充: 求解动态规划问题的四个步骤 解决两个字符串的动态规划问题,一般都是先用两个指针i, j分别指向两个字符串的开始或者最后,然后再一步步向前走, 缩小问题的规模。 假设需...
  • 作者:P.yh理论解析上一次 解释了动态规划的一些基本特性和解题思路,也说了动态规划其实就是记住之前问题的答案,然后利用之前问题的答案来分析并解决当前问题,这里面有两非常重要的步骤,就是 拆解问题 和 定义...
  • 动态规划

    2014-05-20 17:15:00
    要点三:算法设计包含四个步骤: (1)描述最优解结构; (2)递归定义最优解值; (3)按自底向上方式计算最优解值; (4)由计算出结果构造一个最优解。 要点四:应用动态规划的前提有两个:(1)
  • 动态规划初级

    2020-11-21 17:19:52
    *一般解决动态规划问题,分为四个步骤,分别是 ①问题拆解,找到问题之间具体联系 ②状态定义,例如,dp[i]表示当前第i步最优解 ③递推方程推导,找出状态方程,dp[i]与前面最优解之间关系,如dp[i]=dp[i-1]+...
  • 动态规划理论

    2019-08-12 20:54:51
    但是没有说出动态规划本质的特色,像贪心算法三个步骤一样,本篇文章将主要围绕解题思路来讲,目的是让大家明白什么样的问题可以使用动态规划算法,解决动态规划问题的思路 是什么样的,贪心算法、分治算法、回溯...
  • 动态规划----数塔问题

    千次阅读 2012-02-02 19:47:55
    动态规划(Dynamic Programming,简称DP)是通过组合子问题的解来解决问题的。 注意这里的programming不是指编程,而是指一种规划 适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题,鉴于会重复...
  • 目录动态规划与字符串编辑距离动态规划基本思想四个步骤三个例子 动态规划与字符串编辑距离 动态规划 动态规划(dynamic programming)是解决多阶段决策问题常用最优化理论,该理论由美国数学家Bellman等人...
  • 实验要求:分别用伪代码或流程图或步骤分析图描述利用动态规划、贪心策略、回溯法算法解决方案,再用程序实现,计算时间复杂度,记录最终测试数据和测试结果,运行时间。 旅行商问题 问题描述:给定一个的整数矩阵...
  • 菜鸟LeetCode-动态规划

    2020-08-22 22:59:14
    目录动态规划一、动态规划的思想二、动态规划适用情况三、动态规划模板步骤四、相关练习300. 最长上升子序列674. 最长连续递增序列5. 最长回文子串516. 最长回文子序列72. 编辑距离198. 打家劫舍213. 打家劫舍 II ...
  • 动态规划和贪心算法

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

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

    2020-08-23 16:43:17
    动态规划仅仅解决问题一次,具有天然剪枝功能,从而减少计算量 某个给定子问题已算出,则将其存储,以便解决下一相同子问题时直接查表 三、步骤: 确定动态规划状态 写出状态转移方程 考虑初始化条件 考虑...
  • 动态规划的四个步骤: 1)描述最优解的结构; 2)递归定义最优解的值; 3)按自低向上的方式计算最优解的值(首先找到子问题的最优解,解决子问题,最后找到问题的一个最优解); 4)由计算出的结果构造一个最优...
  • 二、【能用】动态规划解决的问题 三、【适合用】动态规划解决的问题 、动态规划求解3关键步骤 1. 建立状态转移方程 2. 缓存小规模答案以复用,避免重复计算 3. 按规模顺序从小到大求解,且最小...
  • 动态规划(DP)理论

    2019-08-10 15:13:54
    就像贪心算法的三个步骤一样,直抒胸臆,于是这篇专栏便会主要围绕着解题思路来讲,目的就是让大家明白什么样的问题可以使用动态规划算法,解决动态规划问题的思路是什么样的,贪心,分治,回溯,动态规划种算法...
  • 动态规划全总结(2)

    2019-11-23 17:20:50
    上一次解释了动态规划的一些基本特性和解题思路,也说了动态规划其实就是记住之前问题的答案,然后利用之前问题的答案来分析并解决当前问题,这里面有两非常重要的步骤,就是拆解问题和定义状态。 这次来针对具体...
  • 算法分析--动态规划

    2021-01-04 21:15:46
    一、动态规划的基本思想:求解问题分为多阶段或多个子问题,然后按顺序求解各个问题,最后一子问题就是初始问题的解。 动态规划=贪婪策略+递推+存储递推结果 空间换取时间 二、主要概念 阶段:把问题分为几...
  • 目录0. 首先,先大致列下这篇文章会讲到什么 1.相较于暴力解法,动态规划带给我们是什么?为什么会有重叠子问题以及... 后 动态规划解决 3. 动态规划 + 优化 二、动态规划四大解题步骤处理问题 案例一:打家...
  • 文章目录动态规划 - 超详细系列首先,先大致列下这篇文章会讲到什么1.相较于暴力解法,动态规划带给我们是什么?... 后 动态规划解决3. 动态规划 + 优化二、动态规划四大解题步骤处理问题步骤一:定义dp数组...
  • 动态规划(dynamic programming)是一种高效程序设计技术,一般应用与最优化问题,... 动态规划算法的解决一个问题,可以分成四个步骤:  1)描述最优解结构,需找最优子结构  2)递归定义最优值解  3)自...

空空如也

空空如也

1 2 3 4 5
收藏数 92
精华内容 36
关键字:

动态规划解决问题的四个步骤