| by YoungTimes | No comments

面试刷题-动态规划-求解最短路径

题目链接

https://leetcode-cn.com/problems/minimum-path-sum/

题目描述

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

[……]

继续阅读

Read More
| by YoungTimes | No comments

机器人动态规划(Dynamic Programming)入门

 1、什么是动态规划

CS专业出身的人大抵没有人不知道动态规划(Dynamic Programming)的,该算法的本质就是把复杂的大问题分解成相互重叠的简单子问题,将子问题的最优解层层组合起来,就得到了复杂大问题的最优解。

能用动态规划解决的问题必须满足两个条件:一是最优子结构。即问题[……]

继续阅读

Read More
| by YoungTimes | No comments

动态规划-最长公共子序列

1.公共子序列

给定两个字符串m和n,如果它们的子串a和b内容相同,则称a和b是m和n的公共子序列。子串中的字符在原字符串中不要求连续,只要保持原有相对顺序即可。

例如,字符串“abcfbc”和“abfcab”,其中“abc”同时出现在两个字符串中,因此“abc”是它们的公共子序列。

[……]

继续阅读

Read More