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

动态规划

要想从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 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

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

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

29610
来自专栏Android机动车

数据结构学习笔记——算法

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表达一个或者多个步骤。

641
来自专栏数据结构与算法

求细胞个数

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如: 阵列  4  10 02...

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

Puyo-Puyo设计文档

2095
来自专栏C语言及其他语言

【每日一题】问题 1429[蓝桥杯][历届试题]兰顿蚂蚁

题目描述 ? 兰顿蚂蚁,是于1986年,由克里斯·兰顿提出来的,属于细胞自动机的一种。 平面上的正方形格子被填上黑色或白色。在其中一格正方形内有...

2846
来自专栏java达人

分治法

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

1898
来自专栏mathor

第五届蓝桥杯决赛B组C/C++——殖民地

1645
来自专栏大数据

大数据图:循环点阵

本文的内容最初由Marko Rodriguez和Bobby Norton在Aurelius博客上共同撰写。

3125
来自专栏北京马哥教育

高阶实战 | 如何用Python检测伪造的视频

译者注:本文以一段自打24小时耳光的视频为例子,介绍了如何利用均值哈希算法来检查重复视频帧。以下是译文。 有人在网上上传了一段视频,他打了自己24个小时的耳光。...

3265
来自专栏大数据文摘

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

2323

扫码关注云+社区