JavaInterview
  • README
  • 架构篇
    • 分布式一致性协议
    • 设计模式
    • ElasticSearch
    • MySQL
    • Redis
    • UML 图总结
  • 大数据篇
    • Hadoop 架构
    • Hive
    • Hive 函数
    • kafka_1
    • MaxList以及Set模块
  • 书籍总结
  • 代码篇
    • 动态规划(Dynamic Programming)
    • order_print_num
  • IO 篇
    • 多线程 N 次写文件
    • 多线程、进程、多核 CPU 详细介绍
  • Java 基础知识
    • 异常介绍
    • StringBuffer 和 StringBuilder
    • 线程池
    • 数据结构篇
      • BlockingQueue 和 BlockingDeque 内部实现分析
    • Java8
    • 关键字篇
      • 关键字-transient
      • 关键字-volatile
  • 深入浅出 JVM
    • garbage_collectors
    • JVM 参数
  • README
  • machinelearning
    • model
    • 推荐系统整理
    • tensorflow 入门
  • 排序篇
    • 冒泡排序
    • 基数排序
    • 选择排序
    • 插入排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 堆排序
    • 计数排序
    • 桶排序
  • Web 篇
    • JavaWeb 中 POJO、BO、VO、DO、DTO、DAO、PO 详细介绍
    • Filter 和 Interceptor 详解
    • HTTP 请求的完整过程
    • Spring 配置
    • Spring IoC
    • Spring 全家桶
Powered by GitBook
On this page
  • 爬楼梯问题
  • 递归方式
  • 从递归到动态规划
  • 详解动态规划
  • 国王和金矿问题
  • 问题描述

Was this helpful?

  1. 代码篇

动态规划(Dynamic Programming)

动态规划其实和分治策略是类似的,也是将一个原问题分解为若干个规模较小的子问题,递归的求解这些子问题,然后合并子问题的解得到原问题的解。 区别在于这些子问题会有重叠,一个子问题在求解后,可能会再次求解,于是我们想到将这些子问题的解存储起来,当下次再次求解这个子问题时,直接拿过来就是。 其实就是说,动态规划所解决的问题是分治策略所解决问题的一个子集,只是这个子集更适合用动态规划来解决从而得到更小的运行时间。 即用动态规划能解决的问题分治策略肯定能解决,只是运行时间长了。因此,分治策略一般用来解决子问题相互对立的问题,称为标准分治,而动态规划用来解决子问题重叠的问题。

将 动态规划 的概念关键点抽离出来描述就是这样的:

  • 动态规划法试图只解决每个子问题一次。

  • 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。

爬楼梯问题

下面通过爬楼梯问题来分析使用动态规划的解决问题(该问题也是在现场面试中遇到的)。

问题描述:爬楼梯,我们每次可以走 1 级阶梯或者 2 级阶梯,那我们走 50(n) 级阶梯总共有多少种走法。 在现场思考过程中,如果没有使用动态规划的话,那就要用递归的概念去做。

递归方式

我们在高中的数学课里面应该学习过规律推理,那我们可以很容易的去推理出来公式: 1 级台阶: 1 种走法(f(1)) 2 级台阶: 2 种走法(f(2)) 3 级台阶: 3 种走法(f(3) = f(2) + f(1)) 4 级台阶: 5 种走法(f(4) = f(3) + f(2)) 5 级台阶: 8 种走法(f(5) = f(4) + f(3)) ... n 级台阶: f(n) = f(n-1) + f(n-2) (n > 2)

通过以上公式,很容易推导出一下递归代码:

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

code:

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

从递归到动态规划

还是以爬台阶为例,如果以递归的方式解决的话,那么这种方法的时间复杂度为O(2^n)

详解动态规划

动态规划中包含三个重要的概念:

  • 最优子结构

  • 边界

  • 状态转移公式

在爬台阶问题中:

f(10) = f(9) + f(8) 是最优子结构 f(1) 与 f(2) 是边界 f(n) = f(n-1) + f(n-2) 状态转移公式

爬台阶问题只是动态规划中相对简单的问题,因为它只有一个变化维度,如果涉及多个维度的话,那么问题就变得复杂多了。

难点就在于找出动态规划中的这三个概念。感觉跟我们高中学习的推理证明题有点像,通过现在的条件推断出结果。

国王和金矿问题

问题描述

有一个国家发现了 5 座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。参与挖矿工人的总数是 10 人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?

Previous代码篇Nextorder_print_num

Last updated 5 years ago

Was this helpful?