什么是动态规划——从青蛙跳台阶开始了解

本文转载自微信公众号「Java极客技术」，作者鸭血粉丝。转载本文请联系Java极客技术公众号。

成都创新互联公司技术团队十多年来致力于为客户提供网站建设、成都做网站、成都品牌网站建设、网络营销推广、搜索引擎SEO优化等服务。经过多年发展，公司拥有经验丰富的技术团队，先后服务、推广了上千网站，包括各类中小企业、企事单位、高校等机构单位。

Hello 大家好，我是阿粉，动态规划(Dynamic Programming)，简称 DP 相信大家在日常的工作或者学习的过程中都遇到过这个词，而且动态规划也是面试过程中最喜欢被问到的题目，阿粉在经历的不多的几场面试中都被问到了，实在是苦不堪言，不过好在阿粉还是有学过的，一些简单的套路阿粉还是懂的。下面就从一个很多人应该都不陌生的题目讲起。

案例 1

问：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级，求该青蛙跳上一个 n 级的台阶总共有多少种跳法?

思考

刚开始看到这个题目的时候可能没什么思路，不过我们可以一点点的想下去，我们假设青蛙跳上一个 n 级的台阶总共有多少种跳法 f(n)种跳法，那当 n = 0 时，f(0) = 0，没有台阶当然没有跳法。n = 1，f(1) = 1;只有一个台阶的时候，只能跳 1 个;n = 2，f(2) = 2，当有两个台阶的时候，可以有 2 种跳法，一个一个跳和一下跳 2 个，那如果我们有三个台阶的话，是不是将一个台阶和两个台阶的总和加起来就可以了呢?所以我们就可以想到 f(3) = f(2) + f(1)，所以我们能推导出 f(n) = f(n - 1) + f(n - 2);

编码

上面的分析可以想到，那么接下来我们就需要用代码来实现了，对于需要使用到之前的记录，我们可以考虑用一维数组来记录，所以就有了下面的这段代码。

 
 
 
 

  
  
  
  
public int dp(int n) { 
  
  
  
  
    if (n <= 0) { 
  
  
  
  
        return 0; 
  
  
  
  
    } 
  
  
  
  
    int[] dp = new int[n + 1]; 
  
  
  
  
    dp[0] = 0; 
  
  
  
  
    dp[1] = 1; 
  
  
  
  
    dp[2] = 2; 
  
  
  
  
   // 之所以要从 3 开始，是因为 2 不符合下面的规则 
  
  
  
  
    for (int i = 3; i <= n; i++) { 
  
  
  
  
        dp[i] = dp[i - 1] + dp[i - 2]; 
  
  
  
  
    } 
  
  
  
  
    return dp[n]; 
  
  
  
  
} 
 
 
 
 

解释下上面的代码，首先我们创建了一个一维数组 dp，用于记录每个台阶有的跳法，然后从索引三开始遍历，运用公式f(n) = f(n - 1) + f(n - 2); 进行赋值，结果直接输出 dp[n] 对应的数值即可。

分析

通过上面的案例，我们思考一下对于动态规划的题目我们需要怎么做，我们一开始定义了 n 级台阶有 f(n) 种跳法，然后通过模拟的方式计算出f(0),f(1),f(2)，接着我们找到了 f(n) = f(n - 1) + f(n - 2); 的关系。按照这种思路我们可以总结出三个步骤，分别是

1. 定义变量：把已知的和需要求解的，定义出变量，如上面的 n 和 f(n);
2. 寻找表达式：找到 f(n) 和 f(n - 1) 以及 f(n - 2)，等情况的表达式，如上面的 f(n) = f(n - 1) + f(n - 2)，这一步往往是最难的;
3. 寻找初始值：确保找到所有的临界条件，如上面的 f(0) = 0, f(1) = 1, f(2) = 2;

上面的步骤是通用步骤，往往在第一步的时候我们设置的 f(n) 是一个数组，根据具体的场景可能是一维数组也有可能是二维数组，上面的例子我们定义的就是一维数组，而且往往我们需要求解什么就定义什么数组。

下面我们通过这种方式再看一道 LeetCode 的原题

案例 2

问：一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?

img

根据上面的三个步骤，我们依次来解决，既然是 m x n 的网格，很显然我们需要用二维数组来解决问题，所以我们

1. 定义 d[m][n] 表示在 m x n 网格上移到右下角需要的总步数;
2. 因为机器人只能向右和向下移动，所以到达下一个格子只能是从左边或者上面，所以达到 m x n 的步数等于(m - 1) x n + m x (n - 1)，也就是 d[m][n] = d[m - 1][n] + d[m][n - 1];
3. 定义初始值d[0][n] = 1，d[n][0] = 1，也就是只有一行或者一列的时候只有一种方法，全部向下或者向右移动;

编码

 
 
 
 

  
  
  
  
public int dp(int m, int n) { 
  
  
  
  
    if (m <=0 || n <= 0) { 
  
  
  
  
        return 0; 
  
  
  
  
    } 
  
  
  
  
    int[][] dp = new int[m][n]; 
  
  
  
  
    //只有一列的时候 
  
  
  
  
    for (int i = 0; i < m; i++) { 
  
  
  
  
        d[i][0] = 1; 
  
  
  
  
    } 
  
  
  
  
    //只有一行的时候 
  
  
  
  
     for (int i = 0; i < n; i++) { 
  
  
  
  
        d[0][i] = 1; 
  
  
  
  
    } 
  
  
  
  
    
  
  
  
  
    for (int i = 1; i < m; i++) { 
  
  
  
  
        for (int j = 1; j < n; j++) { 
  
  
  
  
            d[i][j] = d[i][j - 1] + d[i - 1][j]; 
  
  
  
  
        } 
  
  
  
  
    } 
  
  
  
  
    //数组的下标从 0 开始 
  
  
  
  
    return d[m - 1][n - 1]; 
  
  
  
  
} 
 
 
 
 

通过上面的三个步骤，我们可以完美的解决问题，动态规划的问题难点就在于找寻规律和初始值，有点时候如果我们找不到规律就没办法了，而且如果初始值找的不完全也会有问题，这个只能多多练习了。

总结

动规划的题目在 LeetCode 上面有很多，大家可以根据上面提供的思路去多刷几道题，慢慢就会有感觉了，刷完动态规划的题目，相信对大家工作或者找工作肯定有很大的帮助。

新闻标题：什么是动态规划——从青蛙跳台阶开始了解
浏览路径：http://www.mswzjz.com/qtweb/news48/169348.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联