27 天前 / 噶牛爱尚
0. intro很有意思的问题。以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不应该是这样的。恰好我给入门者讲过四次DP入门，迭代出了一套比较靠谱的教学方法，所以今天跑过来献丑。 现在，我们试着自己来一步步“重新发明”DP。 1. 从一个生活问题谈起先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。 依据生活经验......
55 天前 / 超人汪小建
前言推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。 最长公共子序列最长公共子序列，英文为Longest Common Subsequence，缩写LCS。一个序列，如果是某两个或多个已知序列的最长子序列，则称为最长公共子序列。 另外，要注意的是最长公共子序列与最长公共子串不一样，下面看一个例子就明白。 有序列S1和S2，其中S1=hello，S2=hero。那么最长公共子序列为heo，而最长公共子串为he。可以看到区......
160 天前 / 超人汪小建
前言推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。 Floyd算法Floyd是一种经典的多源最短路径算法，它通过动态规划的思想来寻找给定加权图中的多源点之间的最短路径，算法时间复杂度是O(n3)。之所以叫Floyd是因为该算法发明人之一是Robert Floyd，他是1978年图灵奖获得者，同时也是斯坦福大学计算机科学系教授。 image核心思想对于n个点的加权图，从加权图的权值矩阵开始，递归地更新n次最终......
315 天前 / 超人汪小建
前言 目前计算句子相似性有很多不同的方案，比如基于语义词典的方法、基于相同词汇的方法、基于统计的方法和基于编辑距离的方法。这篇文章先介绍编辑距离的基础。编辑距离 编辑距离其实就是指把一个字符串转换为另外一个字符串所需要的最小编辑操作的代价数。包括插入字符、替换字符和删除字符。编辑距离越小，相似度越大。比如我们要将what转换成where，可能是将 a -> ...
473 天前 / gansteed
这是我本人近段时间学习和练习动态规划的总结，因为本人不是练过ACM的，所以自称民科。文章末尾是一些有用的引用。动态规划(Dynamic Programming)，一听就是一个高大上的词语，我们先来看看维基百科是怎么说的：动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问...
726 天前 / Three_ZJ
前言动态规划很早就接触过了，但一直都心存疑惑。网上的一些文章，基本都是满篇术语。状态转移，状态方程，这种名词，其实是让初学者比较迷惑。直到我上完Berkeley的CS 61 A, 突然就理解了所谓的动态规划。或者说是真正的理解了递归。把玩函数式语言对理解递归，或者说程序结构，非常有帮助。SICP 这本书已经很多人推荐了，用Scheme讲的，我没看完，看了大概...
726 天前 / swoole@桶哥
之前简单介绍了动态规划的概念和解题步骤，但是学习中感觉动态规划的应用范围太灵活了，这里就挑一些常见的题目多练习一下。1、最长公共子序列（字符串相关） 给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。例如：例如：给出"ABCD"和"EDCA"，这个LCS是 "A"(或 D或C)，返回1；给出"ABCD" 和 "EACB"，这个LCS是"AC"返...