Java面试之动态规划与组合数

最近在刷力扣上的题目,刷到了65不同路径,当初上大学的时候,曾在hihocoder上刷到过这道题目,但是现在已经几乎全忘光了,大概的知识点是动态规划,如今就让我们一起来回顾一下。

从题目说起

题目原文是:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

问总共有多少条不同的路径?

例如,上图是一个7 x 3 的网格。有多少可能的路径?

说明:m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2

输出: 3

解释:

从左上角开始,总共有 3 条路径可以到达右下角。

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3

输出: 28

正向思路

我们先按照正常思路来想一下,当你处于起点时,你有两个选择,向右或者向下,除非你处于最下面一排或者最右边一列,那你只有一种选择(比如处于最下面一排,你只能往右),其他位置,你都有两种选择。

因此,我们就根据这个思路,可以写出代码:

class Solution {
  public int uniquePaths(int m, int n) {
    // 特殊情况:起点即终点
    if (m == 1 && n == 1) {
      return 1;
    }
    // 当前处于(1,1),终点为(m,n)
    return walk(1, 1, m, n);
  }
  public int walk(int x, int y, int m, int n){
    // 已经处于终点
    if (x >= m && y >= n) {
      return 0;
    }
    // 处于最下面一排或者最右边一列
    if (x >= m || y >= n) {
      return 1;
    }
    // 往下走,有多少种走法
    int down = walk(x, y + 1, m, n);
    // 往右走,有多少种走法
    int right = walk(x + 1, y, m, n);
    // 从当前(x,y)出发,走到(m,n),共有多少种走法
    return down + right;
  }
}

优化

我们考虑一下,这种写法,有没有可以优化的地方。

你们应该一眼就发现,walk方法的第一个判断if (x >= m && y >= n),永远都不可能为true,因为下一个判断if (x >= m || y >= n)就已经是临界点情况,直接就已经有返回值,根本不可能达到x >= m && y >= n的情况。因此,该判断可以删除。

假设我们从(1,1)的位置出发,终点是(3,3),那么到达(2,2)这个中间点的话有几种走法呢?两种,先到(1,2)再到(2,2),或者,先到(2,1)再到(2,2)。

因此,如果根据我们上面的写法,从(2,2)到终点(3,3),我们会算两次,虽然这样的思路本身是正确,但这样的情况应该是可以优化的。因为从(1,1)到(3,3),一共只有6种路径,但已经有2条是重复的路径了,那么随着m与n越来越大,中间点会越来越多,那么重复的路径也会越来越多。

这就是前面的选择对于后面的选择会有影响,即使后面的选择相同,但由于前面的选择不同,从而也被认为是不同的选择。

很明显,后面的选择更加唯一,如果我们先在后面做出选择,那么就可以减少重复计算的次数。因此,我们可以试试反向思路。

反向思路

如果我们不是从起点出发,而是从终点倒退到起点开始算的话。假设终点是(3,3),它只能由(2,3)和(3,2)直接到达,(2,3)也只能由(2,2)和(1,3)直接到达,(1,3)只能由(1,2)直接到达,(1,2)只能由(1,1)直接到达,因此(1,3)只能由(1,1)直达。

我们可以得出规律:除了最左边一列和最上面一排的点,只能由起点(1,1)直达以外,其他的点(x,y)都是由(x-1,y)和(x,y-1)两个点直接到达的。

因此,根据这个思路,我们可以写出代码:

class Solution {
  public int uniquePaths(int m, int n) {
    int[][] result = new int[m][n];
    int j;
    for (int i = 0; i < m; i++) {
      for (j = 0; j < n; j++) {
        if (i == 0 || j == 0) {
          // 最上面一排的点和最左边一列的点,只能由(1,1)到达
          result[i][j] = 1;
        } else {
          // 其他的点都可以由左边的点和上面的点到达
          result[i][j] = result[i - 1][j] + result[i][j - 1];
        }
      }
    }
    return result[m - 1][n - 1];
  }
}

其实这样的想法就已经是动态规划的范畴了,我们看看维基上的定义

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

一开始我感觉很像分治法,因为都需要将一个大问题分解为子问题,但分治法最终会将子问题合并,但动态规划却不用。

优化

我们考虑一下,这种写法,有没有可以优化的地方。

首先是空间上的优化,我们一定要用二维数组吗?可以用一维数组代替吗?

答案是肯定的,因为每个点的计算只和左边与上边相邻的点有关,因此,不需要更加久远的点。

一维数组

假如只用一维数组,那么只需要存储上一排的结果,如果计算到下一排的时候,则依次替换,代码为:

class Solution {
  public int uniquePaths(int m, int n) {
    int[] dp = new int[m];
    int j;
    for(int i = 0; i < n; i++) {
      for(j = 0; j < m; j++) {
        if(j == 0) {
          dp[j] = 1;
        }
        else {
          // 其他的点都可以由左边的点和上面的点到达
          dp[j] += dp[j-1];
        }
      }
    }
    return dp[m-1];
  }
}

这样的优化,差不多就结束了。那我们是否可以从思路上进行优化呢?

组合数

因为我们只有向右或向下两种选择,而我们一共要走的路径其实是(m-n-2),其中有(m-1)的路径是向右,(n-1)的路径是向下,其实可以转变为:

从(m-n-2)中挑出(m-1),即组合数C((m-n-2), (m-1))的值

那么我们可以写出代码:

class Solution {
  public int uniquePaths(int m, int n) {
    // 用double,因为计算出的数值会很大
    double num = 1, denom = 1;
    // 找出更小的数,这样可以减少计算次数和计算出的数值
    int small = m > n ? n : m;
    for (int i = 1; i <= small - 1; ++i) {
      num *= m + n - 1 - i;
      denom *= i;
     }
     return (int)(num / denom);
  }
}

总结

以上所述是小编给大家介绍的Java面试之动态规划与组合数,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

(0)

相关推荐

  • Java动态规划之硬币找零问题实现代码

    动态规划的基本思想是将待求解问题分解成若干个子问题,先求解子问题,并将这些子问题的解保存起来,如果以后在求解较大子问题的时候需要用到这些子问题的解,就可以直接取出这些已经计算过的解而免去重复运算.保存子问题的解可以使用填表方式,例如保存在数组中. 用一个实际例子来体现动态规划的算法思想--硬币找零问题. 问题描述: 假设有几种硬币,并且数量无限.请找出能够组成某个数目的找零所使用最少的硬币数.例如几种硬币为[1, 3, 5], 面值2的最少硬币数为2(1, 1), 面值4的最少硬币数为2(1,

  • Java常见面试题之多线程和高并发详解

    volatile 对 volatile的理解 volatile 是一种轻量级的同步机制. 保证数据可见性 不保证原子性 禁止指令重排序 JMM JMM(Java 内存模型)是一种抽象的概念,描述了一组规则或规范,定义了程序中各个变量的访问方式. JVM运行程序的实体是线程,每个线程创建时 JVM 都会为其创建一个工作内存,是线程的私有数据区域.JMM中规定所有变量都存储在主内存,主内存是共享内存.线程对变量的操作在工作内存中进行,首先将变量从主内存拷贝到工作内存,操作完成后写会主内存.不同线程间

  • Java基于动态规划法实现求最长公共子序列及最长公共子字符串示例

    本文实例讲述了Java基于动态规划法实现求最长公共子序列及最长公共子字符串.分享给大家供大家参考,具体如下: 动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题.简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加. 为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法. [问题] 求两字符序列的最长公共字符子序列 问题描述:字符

  • Java矩阵连乘问题(动态规划)算法实例分析

    本文实例讲述了Java矩阵连乘问题(动态规划)算法.分享给大家供大家参考,具体如下: 问题描述:给定n个矩阵:A1,A2,...,An,其中Ai与Ai+1是可乘的,i=1,2...,n-1.确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少.输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数. 问题解析:由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序.这种计算次序可以用加括号的方式来确定.若一个矩阵连乘积的计算次序完全确

  • Java面试之动态规划与组合数

    最近在刷力扣上的题目,刷到了65不同路径,当初上大学的时候,曾在hihocoder上刷到过这道题目,但是现在已经几乎全忘光了,大概的知识点是动态规划,如今就让我们一起来回顾一下. 从题目说起 题目原文是: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为"Start" ). 机器人每次只能向下或者向右移动一步.机器人试图达到网格的右下角(在下图中标记为"Finish"). 问总共有多少条不同的路径? 例如,上图是一个7 x 3 的网格.有多少可能

  • java面试常见问题之Hibernate总结

    主要从以下十几个方面对Hibernate做总结,包括Hibernate的检索方式,Hibernate中对象的状态,Hibernate的3种检索策略是什么,分别适用于哪种场合,ORM解决的不匹配问题, Hibernate映射继承关系的3种方式,Session的find()方法以及Query接口的区别等方面问题的总结,具体内容如下: 1  Hibernate的检索方式 Ø  导航对象图检索(根据已经加载的对象,导航到其他对象.) Ø  OID检索(按照对象的OID来检索对象.) Ø  HQL检索(使

  • 详解Java面试官最爱问的volatile关键字

    本文向大家分享的主要内容是Java面试中一个常见的知识点:volatile关键字.本文详细介绍了volatile关键字的方方面面,希望大家在阅读过本文之后,能完美解决volatile关键字的相关问题.  在Java相关的岗位面试中,很多面试官都喜欢考察面试者对Java并发的了解程度,而以volatile关键字作为一个小的切入点,往往可以一问到底,把Java内存模型(JMM),Java并发编程的一些特性都牵扯出来,深入地话还可以考察JVM底层实现以及操作系统的相关知识. 下面我们以一次假想的面试过

  • Java面试必备之AQS阻塞队列和条件队列

    一.AQS入队规则 我们仔细分析一下AQS是如何维护阻塞队列的,在独占方式获取资源的时候,是怎么将竞争锁失败的线程丢到阻塞队列中的呢? 我们看看acquire方法,这里首先会调用子类实现的tryAcquire方法尝试修改state,修改失败的话,说明线程竞争锁失败,于是会走到后面的这个条件: 这个addWaiter方法就是将当前线程封装成一个Node.EXCLUSIVE类型的节点,然后丢到阻塞队列中: 第一次还没有阻塞队列的时候,会到enq方法里面,我们仔细看看enq方法 enq()方法中,我们

  • 吊打Java面试官!整理了一周的Spring面试大全(附答案)

    目录 Q1:什 么 是 spring? Q2:使 用 Spring 框 架 的 好 处 是 什 么 ? Q3:使 用 Spring 缺点是什么? Q4:IoC 是什么? Q5:IOC的优点是什么 Q6:IoC 容器初始化过程? Q7:依赖注⼊的实现方法有哪些? Q8:依赖注入的相关注解? Q9:依赖注入的过程? Q10:Bean 的生命周期? Q11:Bean 的作⽤范围? Q12:如何通过 XML ⽅式创建 Bean? Q13:Spring 有几种配置方式? Q14:如何用基于 XML 配置的

  • 吊打Java面试官之Lambda表达式 Stream API

    目录 一.jdk8新特性简介 二.Lambda表达式 简单理解一下Lambda表达式 Lambda表达式的使用 三.函数式接口 1.什么是函数式接口 2.如何理解函数式接口 3.Java内置四大核心函数式接口 四.方法引用与构造器引用 方法引用 构造器引用和数组引用 五.Stream API 1.Stream API的说明 2.为什么要使用Stream API 3.创建Stream的四种方式 4.Stream的中间操作及其测试 5.Stream的终止操作及其测试 六.Optional类的使用 O

  • Java面试必问之ThreadLocal终极篇分享

    目录 前言 ThreadLocal是什么 ThreadLoalMap hash冲突 内存泄露 如何避免内存泄露 总结 前言 在面试环节中,考察"ThreadLocal"也是面试官的家常便饭,所以对它理解透彻,是非常有必要的. 有些面试官会开门见山的提问: "知道ThreadLocal吗?" "讲讲你对ThreadLocal的理解" 当然了,也有面试官会慢慢引导到这个话题上,比如提问"在多线程环境下,如何防止自己的变量被其它线程篡改&qu

  • java面试散列表及树所对应容器类及HashMap冲突解决全面分析

    目录 性能分析 HashMap 产生冲突原因及解决方法 HashMap 解决冲突方法 jdk7 与 jdk8 中HashMap的区别 发生冲突 扩容 使用建议 散列表 Hashmap.hashtable.concurrentHashMap.hashset: 树: treemap.treeset.hashset treeset 继承自 treemap,hashset 继承自 hashmap : 性能分析 Map 是 Java 中的接口,Map.Entry 是 Map 的一个内部接口 Map 提供了

  • Java面试最容易被刷的重难点之锁的使用策略

    目录 一. 乐观锁和悲观锁 1. 字面理解 2. 生活实例 3. 基于版本号方式实现乐观锁 二. 读写锁 1. 理解 2. 用法 三. 重量级锁和轻量级锁 1. 原理 2. 理解 3. 区分用户态和内核态 四. 自旋锁 1. 理解 2. 实现方式 3. 优缺点 五. 公平锁和非公平锁 1. 理解 2. 注意事项 六. 可重入锁和不可重入锁 1. 为什么要引入这两把锁 (1)实例一 (2)实例二 2. 实现方案 七. 面试题 第一题 第二题 第三题 第四题 在多线程的学习中,很多时候都要用到锁,但

  • Java面试为何阿里强制要求不在foreach里执行删除操作

    小二听完就面露喜色,因为两年前,也就是 2021 年,他在<Java 程序员进阶之路>专栏上的第 63 篇看到过这题

随机推荐