搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发

肝!动态规划

CPP后台服务器开发 2020-08-02

肝!动态规划


前言

也许大家听到动态规划这几个字,和我有一样的感觉,这简直是太难了!我好难~

但是,只要你想要去大厂或者知名的互联网公司,这个就是你的第一道难关,过也得过,不过也得过呀~

既然知道了动态规划的重要性,让我们一起肝一下吧~


动态规划的概念

学习动态规划,那就必须要知道动态规划到底是什么玩意儿~

有刷题经验的朋友应该知道,大家都喜欢用DP来命名动态规划的数组,这个起因就在这里:

动态规划:Dynamic Programming,所以我们简称动态规划为DP

动态规划其实是将一个原问题分解为若干个规模较小的子问题,递归的求解这些子问题,然后合并子问题的解得到原问题的解。

这也许是最简单直白的说法了,确实让人最琢磨不透,后续做了案例就知道了~!

大家可能会想到递归算法,确实,递归算法也是将一个问题分解成若干个子问题进行求解的的,但是,这里还是有和很多的区别的;想学习连接递归算法的,请参考:

动态规划一般会将每个解的子问题的解都记录下来,下次碰到同样的子问题的时候 ,直接使用之前记录的结果,就不用重复计算;

动态规划一般是自底向上的求解,而递归一般是自上向下求解;所以,由于重复计算的问题,动态规划的时间复杂度一般会比递归会小很多;后面的案例会介绍到;


动态规划三要素

1、边界

边界问题是动态规划中初始重要的一环,这是决定什么时候返回,什么时候终止递归或者循环;

我们一般找到边界,做一个最优解,然后通过循环来求解最终问题的最优解;比如最常见的楼梯问题,(不知道可以参考案例一),F(1) = 1;f(2) = 2,这个就是这个问题的边界;

注:一般来说,边界都在 n=1和 n=2这两个结果中;


2、最优子结构

前面概念中说话,动态规划是将大问题化解成小问题,比如求一个问题的最优解,那么就求最小问题的最优解,通过上一阶段的问题和下一阶段的问题,进行循环求最优解的方案,得到最终的问题的最优解;


3、动态规划方程

可以这么说,动态规划的核心就是最后这一步,前面两步骤是为这个步骤最好了垫脚石,通过前面的最优子问题的解,通过归纳总结的方式写出最终的方程,如:F(n) = F(n-2)+f(n-1)等;

然后我们使用循环迭代的方法,对问题进行求解;其实每次迭代的核心逻辑就是使用动态规划方程**寻找下一问题的最优解。


4、使用场景

一般使用到动态规划都会带一些明显的字眼,比如最大、最小、最优、最好等等词语,不过也需要大家慧眼识金,到底是不是要用到动态规划


案例分析一(爬楼梯问题)

题目:

假设你现在正在爬楼梯,楼梯有 n 级(1≤n≤50)。每次你只能爬 1级或者 2级,那么你有多少种方法爬到楼梯的顶部?

分析(我们就按照上述讲的三要素来分析)

1.边界

楼梯只有1级,只走一步就行,所以只有一种方案:
当n=1 时:F(N) = F(1) = 1

楼梯有2级,可以走两步或者每次走一步,有两种方案
当n=2 时:F(N) = F(2) = 2

楼梯有3级,可以有1,2、2,1和1,1三种方案进行:
当n=3 时:F(N) = F(3) = 3

通过上面,进行第三步的时候,已经需要开始排列组合了,所以得到的边界为:

F(1) = 1
F(2) = 2

2、最优子结构

依据题目要求,我们得出是问题可以转化出:最多有多少种方案

依据第一步骤可知,F(3)的最优其实是F(1) + F(2)得出的,这里需要第三步骤的推演;

其实,这个题的最后子答案就是依据F(1)F(2)可以得出的;


3、动态规划方程

这里我们接着第一步的方法再写几个:

楼梯只有1级,只走一步就行,所以只有一种方案:
当n=1 时:F(N) = F(1) = 1

楼梯有2级,可以走两步或者每次走一步,有两种方案
当n=2 时:F(N) = F(2) = 2

楼梯有3级,可以有1,2、2,1和1,1三种方案进行:
当n=3 时:F(N) = F(3) = 3

楼梯有4级,可以有1,1,1,1、1,1,2、1,2,1、2,1,1、2,2、三种方案进行:
当n=4 时:F(N) = F(4) = 5

我们总结下规律:

当n=1 时:F(N) = F(1) = 1
    
当n=2 时:F(N) = F(2) = 2

当n=3 时:F(N) = F(3) = 3 = F(2) + F(1) = 3
    
当n=4 时:F(N) = F(4) = 5 = F(3) + F(2) = 5
    
当n=5 时:F(N) = F(5) = 8 = F(4) + F(3) = 8
    
当n=n 时:F(N) = F(n) = F(n-1) + F(n-2

所以,从上面总结归纳后,我们可以得出动态规划方程为:

F(n) = F(n-1) + F(n-2)

有了上面的分析过程和方程,写代码就是轻而易举的事情了:

C++:

int ClimbStairs(int n)
{
 if (n <= 2)
 {
  return n;
 }
 //f(n) = f(n-1) + f(n-2)
 int n1 = 1, n2 = 2;
 int tmp;
 for (int i = 3; i <= n; i++)
 {
  tmp = n1 + n2;
  n1 = n2;
  n2 = tmp;
 }
 return tmp;
}

java:

public class ClimbStairs {
    public static void main(String[] args) {

        int n = FunClimbStairs(3);
        System.out.println("n:" + n);

    }
    public static int FunClimbStairs(int n){
        if(n<=2){
            return n;
        }
        int n1=1,n2=2;
        int tmp = 0;
        for(int i=3;i<=n;i++){
            tmp = n1+n2;
            n1 = n2;
            n2= tmp;
        }
        return tmp;
    }
}



案例二(最大子序和)

题目:

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

示例:

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-subarray 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


分析(我们就按照上述讲的三要素来分析)

1.边界

当输入数组为空时,返回是0;


2、最优子结构

我们一次按照计算的方式:

f(1) = -2
所以f(1)的最优结果是 -2
    
f(2) = -2 + 1 = -1
所以f(1)的最优结果是 -1   
    
f(3) = -2 + 1 + -3 = -4
所以f(1)的最优结果是 -1     


3、动态规划方程

然后我们根据上述来归纳方程:

f(n) = max( nums[n]  , nums[n]  + f(n-1) )

我们用dp[n] 来存储结果:

dp[n] = max(nums[n],nums[n] + dp[n-1])

有了下面的结论,我们可以开始编写代码:

C++代码:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty())
        {
            return 0;
        }
        vector<int>dp(nums.size(),-1);
        dp[0] = nums[0];
        int MaxNum = 0;
        for(int i=1;i<nums.size();i++)
        {
            dp[i] = max(nums[i],nums[i] + dp[i-1]);
            if(dp[i] > MaxNum)
            {
                MaxNum = dp[i];
            }
        }
        return MaxNum;
    }
};

JAVA代码:

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

案例三(最小路径和)

题目:

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:

输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-path-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


分析(我们就按照上述讲的三要素来分析)

1.边界

这里边界我们要考虑的是上边界和左边界,也是就是i = 0和j=0的情况;


2、最优子结构

还是按照原来的方案,我们找最小的:(只能向下或者向右)

起点:dp[0][0],终点是 dp[i][j]

我们将上述问题转化成子问题,求解最优解:

dp[0][0] ---> dp[i][j]
转成成:
dp[0][0] ---> dp[1][1]的最小距离;
dp[1][1] ---> dp[2][2]的最小距离;
...
dp[i-1][j-1]--->dp[i][j]的最小距离;

有了这个,我们就直接可以去推导一下第一个,其他的找规矩就可以:

开始肝~

上面边界求解,已经为我们计算出来边界值:

dp[1][0] = 3
dp[0][1] = 1
所以:dp[1][1] = min(dp[1][0],dp[0][1]) + nums[1][1] = 1 + 5 = 6

这个就是dp[0][0] ---> dp[1][1]的最小距离,那么其他的也就是很类似了,边界求解,存储至dp数组中,然后对子问题优化求解,最终得到的就是dp[i][j]的最小距离;


3、动态规划方程

通过上面的推演,我们很宽就可以写出公式:

dp[i][j]存储的是每个坐标点最小值;

公式:

当i=0;j>0:
dp[0][j] = dp[0][j-1] + nums[0][j];

当j=0;i>0:
dp[i][0] = dp[i-1][0] + nums[i][0];

当i!=0;j!=0:
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + nums[i][j];

有了上述的表达式,代码就自然就出来了:

C++:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty())
        {
            return 0;
        }
        int rows = grid.size();
        int cols = grid[0].size(); 
        vector<vector<int>>dp(rows,vector <int> (cols));
        dp[0][0] = grid[0][0];
        for(int i=1;i<rows;i++)
        {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j=1;j<cols;j++)
        {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for(int i=1;i<rows;i++)
        {
            for(int j=1;j<cols;j++)
            {
                dp[i][j] = min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }
        return dp[rows-1][cols-1];
    }
};

往期精彩文章汇总



冰冻三尺,非一日之寒,水滴石穿,非一日之功,愿我们一起加油努力~

语言:C++ JAVA  python





版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《肝!动态规划》的版权归原作者「CPP后台服务器开发」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注CPP后台服务器开发微信公众号

CPP后台服务器开发微信公众号:CppServer1

CPP后台服务器开发

手机扫描上方二维码即可关注CPP后台服务器开发微信公众号

CPP后台服务器开发最新文章

精品公众号随机推荐