这是一道算法面试题,不妨看看

动态规划

要想从start 点到 finish 点,那么,必然经过 h1 或 h2 点,所以,问题转化为:求 start 点到 h1 点,或 start 点到 h2点的路径中的较小者,这相当于将问题域变小了1,递归下去,直到问题域变为 1 个点,如下图所示,

这是动态规划思想的典型运用,以下是一版 C# 代码的实现,熟悉 JAVA 的看这些代码也没有问题。

public int MinPathSum(int[,] grid) { int m=grid.GetUpperBound(0)+1; //0-dimension element size int n=grid.GetUpperBound(1)+1; //1-dimension element size int[,] sumdp = new int[m,n]; sumdp[0,0]=grid[0,0]; //two boundaries: for (int i = 1; i < m; i++) sumdp[i,0] = sumdp[i-1,0]+grid[i,0]; for (int i = 1; i < n; i++) sumdp[0,i] = sumdp[0,i-1]+grid[0,i]; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { sumdp[i, j] = Math.Min(sumdp[i - 1, j], sumdp[i, j - 1]) + grid[i,j]; } } return sumdp[m - 1, n - 1]; }

动态规划思想最重要的两个点:

  • 找出迭代方程, sumdp[i, j] = Math.Min(sumdp[i - 1, j], sumdp[i, j - 1]) + grid[i,j];
  • 空间复杂度换取时间复杂度,代码中的 int[,] sumdp = new int[m,n];

总结

动态规划思想,是算法面试中经常问到的,大家可以详细参考相关链接中的文章再具体了解下什么样的问题适合用动态规划思想来求解,以及动态规划求解的两个点。

希望大家接下来面试算法岗,被问到动态规划问题时,准确击中要害,成为自己的加分项。

相关链接

动态规划|算法

动态规划|前篇:括号知多少

动态规划|中篇:爬楼梯

动态规划|后篇:考量适用指标

动态规划|约束条件下的三角最短路径

动态规划|相邻约束下的最优解

动态规划|相邻约束下的最优解(House Robber II )

原文发布于微信公众号 - Python与机器学习算法频道(alg-channel)

原文发表时间:2018-04-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据文摘

你真的懂TensorFlow吗?Tensor是神马?为什么还会Flow?

74870
来自专栏AI研习社

文本分类又来了,用 Scikit-Learn 解决多类文本分类问题

在商业领域有很多文本分类的应用,比如新闻故事通常由主题来分类;内容或产品常常被打上标签;基于如何在线谈论产品或品牌,用户被分成支持者等等。

17810
来自专栏开发 & 算法杂谈

动态数据竞争检测方法实验分析(一)

之前的文章大致介绍了一下我们的动态数据竞争检测平台如何构建,这篇文章主要是在动态数据竞争检测平台上实现了之前介绍的数据竞争检测方法,我们扩展了其中的一些方法使得...

23320
来自专栏逍遥剑客的游戏开发

Puyo-Puyo设计文档

22350
来自专栏liuchengxu

STARKs, Part II: Thank Goodness It's FRI-day

在本系列的上一篇文章中,我们谈到了,如何能够做出一些非常有意思且简洁的计算证明,比如通过利用多项式复合和除法技术,证明你算出了第一百万个斐波那契数。但是,它依托...

11710
来自专栏奇点大数据

遗传算法(2)

在遗传算法中我们再举一个求极大值的例子。这种例子也是比较多见的,只要我们把一些数据关系描述成函数之后就会有一些求极大值或者极小值的问题。 其实极大值和极小值是一...

366120
来自专栏灯塔大数据

每周学点大数据 | No.3算法设计与分析理论

No.3期 算法设计与分析理论 在计算机科学中,研究算法的设计和评价算法“好坏”的分支,称为算法设计与分析理论。它研究如何去设计解决问题的算法,同时给出一个对...

306100
来自专栏大数据文摘

改变计算技术的 9 个伟大算法

26430
来自专栏懒人开发

(7.7)James Stewart Calculus 5th Edition:Approximate Integration

黎曼求和,我们把对应的[a, b]分成n份,每份大概为 Δx = (b - a)/n 这个时候,有:

19230
来自专栏java达人

分治法

一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的...

20180

扫码关注云+社区

领取腾讯云代金券