44 天前 / y277an
动态规划算法一直是面试手撕算法中比较有挑战的一种类型。很多的分配问题或者调度问题实际上都可能用动态规划进行解决。（当然，如果问题的规模较大，有时候会抽象模型使用动归来解决，有时候则可以通过不断迭代的概率算法解决查找次优解） 所以，动归很重要，至少算法思想很重要。 什么是动态规划？通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 重叠子问题：在用递归算法自顶向......
64 天前 / 算法与编程之美微信
通过欢迎点击「算法与编程之美」↑关注我们！ 本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。 深入理解动态规划算法 - 凑硬币 深入理解动态规划算法 - 爬楼梯 深入理解动态规划算法 - 凑整数 前面三篇文章已经为大家介绍了利用动态规划算法解决问题的思路以及相关的代码实现，最为核心的就是第一步利用数学中函数的思想来建立模型，然后求解问题。这三个问题构建的数学函数都有一个共同的特征就是所构建的函数都是一元函数即y = f(x)。 如凑硬币的问题“面值为1元、3元、5元的硬币若干，如何......
69 天前 / 算法与编程之美微信
欢迎点击「算法与编程之美」↑关注我们！ 本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。 问题描述 给定正整数n，找出所有不同的写法使得n为整数1，3，4的和。 如：n=5时，不同的写法有5种。 解决方案 下面将介绍利用动态规划的思路来解决问题。 1、 将问题求解转化为函数形式。 从初中开始我们就接触了函数的概念，所谓函数指的就是给定自变量x，根据某种映射规则进行运算后，会得到一个值y。 举个简单的例子来说明，y=2·x就是一种映射关系，如给定x=2，进行运算后可以得到y=2·2=4。 而......
71 天前 / 算法与编程之美微信
欢迎点击「算法与编程之美」↑关注我们！ 本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。 动态规划(Dynamic Programming)算法是计算机科学科学领域中最重要也是最常用的一个算法，巧妙的利用它可以解决很多复杂的问题，而且该算法也频繁的出现在各大互联网公司的面试中，因此掌握它是十分必要的。 但该算法对于初学者来说理解并掌握并非易事，本系列教程将带领大家一起来学习该算法，通过经典的案列介绍和问题分析以及python代码实现，帮助大家彻底理解动态规划。 问题描述 首先我们来看一道非常经典......
118 天前 / 噶牛爱尚
0. intro很有意思的问题。以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不应该是这样的。恰好我给入门者讲过四次DP入门，迭代出了一套比较靠谱的教学方法，所以今天跑过来献丑。 现在，我们试着自己来一步步“重新发明”DP。 1. 从一个生活问题谈起先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。 依据生活经验......
147 天前 / 超人汪小建
前言推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。 最长公共子序列最长公共子序列，英文为Longest Common Subsequence，缩写LCS。一个序列，如果是某两个或多个已知序列的最长子序列，则称为最长公共子序列。 另外，要注意的是最长公共子序列与最长公共子串不一样，下面看一个例子就明白。 有序列S1和S2，其中S1=hello，S2=hero。那么最长公共子序列为heo，而最长公共子串为he。可以看到区......
252 天前 / 超人汪小建
前言推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。 Floyd算法Floyd是一种经典的多源最短路径算法，它通过动态规划的思想来寻找给定加权图中的多源点之间的最短路径，算法时间复杂度是O(n3)。之所以叫Floyd是因为该算法发明人之一是Robert Floyd，他是1978年图灵奖获得者，同时也是斯坦福大学计算机科学系教授。 image核心思想对于n个点的加权图，从加权图的权值矩阵开始，递归地更新n次最终......
406 天前 / 超人汪小建
前言 目前计算句子相似性有很多不同的方案，比如基于语义词典的方法、基于相同词汇的方法、基于统计的方法和基于编辑距离的方法。这篇文章先介绍编辑距离的基础。编辑距离 编辑距离其实就是指把一个字符串转换为另外一个字符串所需要的最小编辑操作的代价数。包括插入字符、替换字符和删除字符。编辑距离越小，相似度越大。比如我们要将what转换成where，可能是将 a -> ...
564 天前 / gansteed
这是我本人近段时间学习和练习动态规划的总结，因为本人不是练过ACM的，所以自称民科。文章末尾是一些有用的引用。动态规划(Dynamic Programming)，一听就是一个高大上的词语，我们先来看看维基百科是怎么说的：动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问...
818 天前 / Three_ZJ
前言动态规划很早就接触过了，但一直都心存疑惑。网上的一些文章，基本都是满篇术语。状态转移，状态方程，这种名词，其实是让初学者比较迷惑。直到我上完Berkeley的CS 61 A, 突然就理解了所谓的动态规划。或者说是真正的理解了递归。把玩函数式语言对理解递归，或者说程序结构，非常有帮助。SICP 这本书已经很多人推荐了，用Scheme讲的，我没看完，看了大概...
818 天前 / swoole@桶哥
之前简单介绍了动态规划的概念和解题步骤，但是学习中感觉动态规划的应用范围太灵活了，这里就挑一些常见的题目多练习一下。1、最长公共子序列（字符串相关） 给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。例如：例如：给出"ABCD"和"EDCA"，这个LCS是 "A"(或 D或C)，返回1；给出"ABCD" 和 "EACB"，这个LCS是"AC"返...