计算机行业是一个发展非常迅速的行业，技术可谓是日新月异。同样，书籍也是更迭不断。书龄在二十年以上的书，少之又少。如果还能一直保持畅销，那绝对是凤毛麟角。而 《程序员修炼之道》 绝对算是这些神品中不可或缺的一本。 最近当当在搞读书节，又成功骗我入坑，买了几本心仪已久的书。《程序员修炼之道·第2版》被我成功收入囊中。打开书本，只看目录就感觉可以值回书价了。99 条提示，字字珠玑，金科玉律。忍不住发篇水文，推波助澜，让其发扬光大。 务实的哲学 关注你的技艺 思考！思考你的工作 你有选择权 提供选择，别找借口 不要放任破窗 做推动变革的催化剂 牢记全景 将质量要求视为需求问题 对知识组合做定期投资 批判性地分析你读到和听到的东西 英语就是另一门编程语言 说什么和怎么说同样重要 把文档嵌进去，而不是拴在表面 务实的方法 优秀的设计比糟糕的设计更容易变更 DRY—​不要重复自己 让复用变得更容易 消除不想搞事物之间的影响 不设最终决定 放弃追逐时尚 使用曳光弹找到目标 用原型学习 靠近问题域编程 通过估算来避免意外 根据代码不断迭代进度表 基础工具 将知识用纯文本保存 发挥 Shell 命令的威力 游刃有余地使用编辑器 永远使用版本控制 去解决问题，而不是责备 不要恐慌 修代码前先让代码在测试中失败 读一下那些该死的出错信息 “select”没出问题 不要假设，要证明 学习一门文本处理语言 务实的偏执 你无法写出完美的软件 通过契约进行设计 尽早崩溃 使用断言去预防不可能的事情 有始有终 在局部行动 小步前进——由始至终 避免占卜 宁折不弯 解耦代码让改变更容易 只管命令不要询问 不要链式调用方法 避免全局数据 如果全局唯一非常重要，那么将它包装到API 中 编程讲的是代码，而程序谈的是数据 不要囤积状态，传递下去 不要付继承税 尽量用接口来表达多态 用委托提供服务：“有一个”胜过“是一个” 利用 mixin 共享功能

最近，D瓜哥的一个小伙伴向我抱怨，Java 并发是个大坑，问我怎么看？我回答，当然是用眼睛看啊… D瓜哥觉得，想学好 Java 并发，最重要的还是啃书。幸运的是，Java 中还是有不少关于并发的优秀书籍可以看。正好利用这个机会，把看过的、个人认为还不错的书推荐一波。没有看过的就不多言了。 Java并发编程实战 如果只选一本书来深入研究并发，那肯定是这本书。 Java并发编程实战 (豆瓣) — 这本书是必看的。JDK 中 JUC 就是这本书的作者们写的。虽然书名含有 Java 一次，但是，里面更多是原理性的东西，各种语言都适用。只是例子少了一些。这本书需要多读几遍。（据说翻译不行，推荐看英文版） 放个英文版图片镇楼： Java并发编程的艺术 Java并发编程的艺术 (豆瓣) — 这本书也不错，讲了很多源码方面的内容，非常棒。另外，在讲解 Double Lock 方面的知识时，涉及了很多 Java Memory Model 方面的知识，可以先看看 深入理解Java虚拟机（第3版）(豆瓣) 最后两章的内容，来提前补充一下这么方面的知识。 实战Java高并发程序设计 实战Java高并发程序设计（第2版） (豆瓣) — 这本书也不错，针对 Java 8 写的，Java 8 中的很多新知识都有涉猎，例子也很全面。广度和深度，得到了兼顾，非常棒。 Java编程思想 Java编程思想（第4版）(豆瓣) — 虽然这本书已经出来十余年了，但是依然经典。第 21 章 并发，用大量的例子和陈述来介绍并发。非常棒。美中不足，是针对 Java 5 编写的，现在已经 Java 8 了。不过，作者又出了一本书，可以理解成升级版。 On Java 8 On Java 8 (豆瓣) — 这是《Java编程思想》的姊妹版和升级版。Bruce Eckel 的写书功底和对语言的理解毋庸置疑。目前中文版还没有正式版，网上已经有热心网友做起来搬运工，感兴趣自行 Google。 Java 9 并发编程实战 Java 9 并发编程实战 (豆瓣) — 入门的话，这本书是不错的选择。每个特性一个例子，整本书大概 80% 的篇幅都是代码。所以，一定也不用担心有读书压力。

现在手机银行转账已经司空见惯。但是，D瓜哥一直在思考，银卡跨行转账是如何保证事务一致性的？借机就对分布式事务，做了简单地了解。 2PC 两阶段提交（2pc， two-phase commit protocol），2pc是非常经典的强一致性、中心化的原子提交协议。中心化是指协议中有两类节点：一个中心化协调者节点（coordinator）和N个参与者节点（participant、cohort）。 顾名思义，两阶段提交协议的每一次事务提交分为两个阶段： 在第一阶段，协调者询问所有的参与者是否可以提交事务（请参与者投票），所有参与者向协调者投票。 在第二阶段，协调者根据所有参与者的投票结果做出是否事务可以全局提交的决定，并通知所有的参与者执行该决定。在一个两阶段提交流程中，参与者不能改变自己的投票结果。两阶段提交协议的可以全局提交的前提是所有的参与者都同意提交事务，只要有一个参与者投票选择放弃(abort)事务，则事务必须被放弃。 两阶段提交协议也依赖与日志，只要存储介质不出问题，两阶段协议就能最终达到一致的状态（成功或者回滚） 优点 强一致性，只要节点或者网络最终恢复正常，协议就能保证顺利结束；部分关系型数据库（Oracle）、框架直接支持 缺点 网络抖动导致的数据不一致： 第二阶段中协调者向参与者发送commit命令之后，一旦此时发生网络抖动，导致一部分参与者接收到了commit请求并执行，可其他未接到commit请求的参与者无法执行事务提交。进而导致整个分布式系统出现了数据不一致。 超时导致的同步阻塞问题： 2PC中的所有的参与者节点都为事务阻塞型，当某一个参与者节点出现通信超时，其余参与者都会被动阻塞占用资源不能释放。 单点故障的风险： 由于严重的依赖协调者，一旦协调者发生故障，而此时参与者还都处于锁定资源的状态，无法完成事务commit操作。虽然协调者出现故障后，会重新选举一个协调者，可无法解决因前一个协调者宕机导致的参与者处于阻塞状态的问题。 基于两阶段提交的分布式事务在提交事务时需要在多个节点之间进行协调,最大限度地推后了提交事务的时间点，客观上延长了事务的执行时间，这会导致事务在访问共享资源时发生冲突和死锁的概率增高，随着数据库节点的增多，这种趋势会越来越严重，从而成为系统在数据库层面上水平伸缩的"枷锁"， 这是很多Sharding系统不采用分布式事务的主要原因。 3PC 三阶段提交协议（3pc Three-phase_commit_protocol）主要是为了解决两阶段提交协议的阻塞问题，从原来的两个阶段扩展为三个阶段，并且增加了超时机制。 3PC 的三个阶段分别是 CanCommit、PreCommit、DoCommit CanCommit 协调者向所有参与者发送CanCommit命令，询问是否可以执行事务提交操作。如果全部响应YES则进入下一个阶段。 PreCommit 协调者向所有参与者发送PreCommit命令，询问是否可以进行事务的预提交操作，参与者接收到PreCommit请求后，如参与者成功的执行了事务操作，则返回Yes响应，进入最终commit阶段。一旦参与者中有向协调者发送了No响应，或因网络造成超时，协调者没有接到参与者的响应，协调者向所有参与者发送abort请求，参与者接受abort命令执行事务的中断。 DoCommit 在前两个阶段中所有参与者的响应反馈均是YES后，协调者向参与者发送DoCommit命令正式提交事务，如协调者没有接收到参与者发送的ACK响应，会向所有参与者发送abort请求命令，执行事务的中断。 3PC只是解决了在异常情况下2PC的阻塞问题，但导致一次提交要传递6条消息，延时很大。 TCC TCC是Try、Commit、Cancel的缩写，TCC在保证强一致性的同时，最大限度提高系统的可伸缩性与可用性。 TCC（Try-Confirm-Cancel）又被称补偿事务，TCC 与 2PC 的思想很相似，事务处理流程也很相似，但 2PC 是应用于在 DB 层面，TCC 则可以理解为在应用层面的 2PC，是需要我们编写业务逻辑来实现。 TCC 的核心思想是："针对每个操作都要注册一个与其对应的确认（Try）和补偿（Cancel）"。 一个完整的业务包含一组子业务，Try操作完成所有的子业务检查，预留必要的业务资源，实现与其他事务的隔离；Confirm使用Try阶段预留的业务资源真正执行业务，而且Confirm操作满足幂等性，以遍支持重试；Cancel操作释放Try阶段预留的业务资源，同样也满足幂等性。“一次完整的交易由一系列微交易的Try 操作组成，如果所有的Try 操作都成功，最终由微交易框架来统一Confirm，否则统一Cancel，从而实现了类似经典两阶段提交协议（2PC）的强一致性。” 再来一个例子： 与2PC协议比较 ，TCC拥有以下特点： 位于业务服务层而非资源层 ，由业务层保证原子性 没有单独的准备(Prepare)阶段，降低了提交协议的成本 Try操作 兼备资源操作与准备能力 Try操作可以灵活选择业务资源的锁定粒度，而不是锁住整个资源，提高了并发度 缺点 应用侵入性强：TCC由于基于在业务层面，至使每个操作都需要有 try、confirm、cancel三个接口。 开发难度大：代码开发量很大，要保证数据一致性 confirm 和 cancel 接口还必须实现幂等性。 在 Seata 中，根据两阶段行为模式的不同，我们将分支事务划分为 Automatic (Branch) Transaction Mode 和 Manual (Branch) Transaction Mode.

MapReduce MapReduce编程模型来自函数式编程，包含两个最基本的算子：map，reduce 将一个运算任务分解成大量独立正交的子任务，每个子任务通过map算子计算，得到中间结果，然后用reduce算子进行聚合，得到最终结果。 这两个算子有一个很重要的特征：确定性的纯过程调用（pure function），函数既不会修改输入，也不存在中间状态，也没有共享的内存。因此，输入一致的情况下，输出也是一致的，这大大方便了容错性设计。 系统中有两类主要的进程节点：master（单点），worker（多个）。其中，worker根据不同的计算任务，又分为map worker（对应上图中的Map phase）、reduce worker（对应上图中的Reduce phase）。 master是系统的中心节点，负责计算任务到worker节点的分配，同时监控worker节点的状态。如果某个worker计算太慢，或者宕机，master会将该worker进程负责的计算任务转移到其他进程。 map worker从GFS（google file system）中读取输入数据，然后将中间结果写到本地文件；reduce worker从master处得知中间结果的问题，通过rpc读取中间文件，计算之后将最终结果写入到可靠存储GFS。生产环境中，一个MapReduce过程的输出通常是另一个MapReduce计算的输入，类似Unix 的 pipeline，只不过unix pipeline通过stdin、stdout连接两个程序，而MapReduce使用GFS连接两个计算过程。 Scalability 由于计算任务的正交性，很容易通过增加map worker、reduce worker来处理计算任务的增长。Input file 到 Map phase这个阶段，使用了基于范围（range based）的分片方法，master作为元数据服务器会记录split到worker的映射关系。 Availability 系统对worker的容错性较好，但对master的容错性较差。 对于map worker，计算结果是写到本地文件，本地文件的位置需要通知到master，即使同一个task被多个map worker执行，单点的master只会采纳一份中间结果。而且上面提到了map function是pure function，所以计算结果也是一样的。 对于reduce worker，reduce task的计算结果会先写到临时文件（temporary file），task完成之后再重命名写入gfs，那么如果一个reduce task再多个reduce worker上计算，那么会不会有问题呢，答案是不会的 Performance data locality — 将任务调度到数据所在的节点进行计算，减少网络传输； backup task — master在发现某个worker上的task进展异常缓慢的时候，会将这个task调度到其他worker，以缩短这个任务（Job）的完成时间。 GFS GFS（Google File System）是Google研发的可伸缩、高可用、高可靠的分布式文件系统，提供了类似POSIX的API，按层级目录来组织文件。 GFS master、GFS Client、GFS chunkserver。其中，GFS master任意时刻只有一个，而chunkserver和gfs client可能有多个。 一份文件被分为多个固定大小的chunk（默认64M），每个chunk有全局唯一的文件句柄 －－ 一个64位的chunk ID，每一份chunk会被复制到多个chunkserver（默认值是3)，以此保证可用性与可靠性。chunkserver将chunk当做普通的Linux文件存储在本地磁盘上。 GFS master是系统的元数据服务器，维护的元数据包括：命令空间（GFS按层级目录管理文件）、文件到chunk的映射，chunk的位置。其中，前两者是会持久化的，而chunk的位置信息来自于Chunkserver的汇报。 GFS master还负责分布式系统的集中调度：chunk lease管理，垃圾回收，chunk迁移等重要的系统控制。master与chunkserver保持常规的心跳，以确定chunkserver的状态。

HTTP1.0 根据谷歌的调查， 现在请求一个网页，平均涉及到 80 个资源，30 多个域名。考虑最原始的情况，每请求一个资源都需要建立一次 TCP 请求，显然不可接受。HTTP 协议规定了一个字段 Connection，不过默认的值是 close，也就是不开启。 HTTP1.1 Pipeline 是为了减少不必要的 TCP 连接，但依然存在队头阻塞(HOC)的缺点，一种解决思路是利用并发连接减少某一个 HOC 的影响，另一个是共享(注意与复用的区别) TCP 连接，直接避免 HOC 问题的发生。 HTTP1.1 的缺陷 高延迟 — 队头阻塞(Head-Of-Line Blocking) 当有多个串行请求执行时，如果第一个请求不执行完，后续的请求也无法执行。 支持并发请求是解决解决 HOC 问题的一种方案，并发请求并非是直接解决了 HOC 的问题，而是尽可能减少 HOC 造成的影响。 将同一页面的资源分散到不同域名下，提升连接上限。 减少请求数量 内联一些资源：css、base64 图片等 合并小文件减少资源数 无状态特性 — 阻碍交互 明文传输 — 不安全性 HTTP 1.x 也可以配合 TLS 进行安全传输，只是不是强制的。 不支持服务端推送 SPDY SPDY 是由 Google 推行的改进版本的 HTTP1.1。 针对 HTTP1.1 的缺陷，SPDY 提供了如下特性： 多路复用 — 解决队头阻塞 SPDY 允许在一个连接上无限制并发流。因为请求在一个通道上，TCP 效率更高。

理智告诉我该走了， 但情感却恋恋不舍； 大脑告诉我放手吧， 但心依旧在沦陷； 认识你让生活诗情画意， 想起你忍不住嘴角上扬， 思念你梦都是甜的。 想做你的指南针， 带你周游世界； 带你翱翔太空； 带你去梦想的远方。 想做你的眼镜， 带你观历史的沧海桑田； 带你赏自然的鬼斧神工； 带你看艺术的侠骨柔情。 想做你的厨师， 可口的早餐等你醒来； 丰盛的晚餐等你回家。 好想用心爱你一次， 爱你就像爱生命； 我挣钱养家，你貌美如花； 我用坚强的臂膀， 构建温馨的家。 即使外面狂风暴雨， 家中依然四季如春。 好想和你站在一起， 勇往直前，彼此成就。 你做园丁， 浇灌祖国的花朵； 我做篝火， 温暖家庭，照亮社会。 想说的话，千言万语， 却不能说出口。 想见的人，魂牵梦绕， 却咫尺天涯。 远远祝福你， 事事顺心，桃李天下。 我渴望爱的垂涎， 但不要怜悯的爱。 我将继续加油， 做生活的愚公， 逢山开路，遇水搭桥。 遥知不是雪，为有暗香来。 知音难觅，弦断有谁听？

这个月断断续续把季凯帆的 《解读基金——我的投资观与实践（修订版）》读完了，秉持读完一本，消化一本的读书理念，做一下读书笔记，整理消化一下书中的内容。 目前房地产不景气，银行利息跑不赢 CPI 的情况下，证券市场是不错的可选性。首先，有政府在背后支撑、监督，不会像 P2P 那样随时暴雷跑路；其次，多方资料显示，长期来看，美国指数基金的收益率在 10% 左右，妥妥跑赢 CPI。第三，流动性好，随手都可以出手（当然有可能会亏损），最长一周时间就可以到账。（节假日除外）第四，起始资金低，几乎没有限制（支付宝买基金十元起步），相比买房动辄几十万，这几乎可以认为没有门槛。实际上，关键的问题是如何投资证券市场。 学习借鉴别人的成功经验是迅速提高自己能力的最佳办法之一。阅读这本书，也是学习别人的成功经验，提高自己的投资能力。 D瓜哥在 “《如何阅读一本书？》之读书笔记” 中介绍了一种读书方法，这次也按照这个读书方法把书的内容梳理一遍。 四个基本问题 一个阅读者要提出的四个基本问题: 整体来说，这本书到底在谈些什么？你一定要想办法找出这本书的主题，作者如何依次发展这个主题，如何逐步从核心主题分解出从属的关键议题来。 作者细部说了什么，怎么说的？你一定要想办法找出主要的想法、声明与论点。这些组合成作者想要传达的特殊讯息。 这本书说得有道理吗？是全部有道理，还是部分有道理？ 这本书跟你有什么关系？ 问题 针对这本书，D瓜哥有如下一下问题： 股市都有哪些风险？ 常说的系统性风险都具体指哪些？ 配置什么样的投资产品？什么比例比较合适？ 基金是怎么运作的？怎么收费的？ 如何选择基金？需要关注哪些方面？ 何时卖出基金？ 场内 ETF 指数基金和场外 ETF 增强基金有啥区别？ 我的操作中，有什么不合理的地方？ 投资准备 总结 投资，说穿了就是让钱生钱。让钱生钱，这其实是所有富人的生财之道。-- D瓜哥觉得把“富人”换成“投资人”更合适。 “富爸爸”和“穷爸爸”最核心的区别是理念，“富爸爸”在投资，让钱生钱；而“穷爸爸”就盯着那点工资，他一生的追求就是寻找一个好的工作，得到一份好的薪水。 投机是瞄准一个“机会”，希望大赚一笔，一劳永逸，而投资是要你扎扎实实、一点一滴地走向你的最终梦想。 基金就是把大家的钱收集到一起，由专门的人（基金经理）帮我们去投资证券市场。他提取他的佣金，我们拿我们的收益，他们帮我们理财投资。 开放式基金，一般分为股票基金、债券基金、货币基金，以及介于股票和债券基金中间的配置型基金。 Charmin综合征 投资不是比智商，而是比谁更理性，而理性的前提就是理解，要理解就得花点时间吧。 摘要 学习借鉴别人的成功经验是迅速提高自己能力的最佳办法之一。 梳理正确的投资观念 投资，说穿了就是让钱生钱。让钱生钱，这其实是所有富人的生财之道。 “富爸爸”和“穷爸爸”最核心的区别是理念，“富爸爸”在投资，让钱生钱；而“穷爸爸”就盯着那点工资，他一生的追求就是寻找一个好的工作，得到一份好的薪水。 《富爸爸穷爸爸》 是一本很赞的书，推荐对投资理财感兴趣的童鞋去看一看。 投机是瞄准一个“机会”，希望大赚一笔，一劳永逸，而投资是要你扎扎实实、一点一滴地走向你的最终梦想。投机实际上更多的是收获风险和灾难，而投资则是一种理性的产物。 基金简介 简单地说，基金就是把大家的钱收集到一起，由专门的人（基金经理）帮我们去投资证券市场。他提取他的佣金，我们拿我们的收益，他们帮我们理财投资。 基金资产的管理与保管是分开的，基金公司管理我们的钱的投资运作，而钱一般是托管在银行的。 一种是在你购买基金的时候缴纳，叫前端收费；也可以选择在卖（赎回）基金的时候缴纳，叫后端收费。 每种基金的净值都是在当天股票交易市场收盘以后再根据其所持有的证券的市值来计算的，一天就一个值，这个值在北京时间下午 3点以后才知道。 在看一个基金的净值时会有两个，一个叫“净值”，一个叫“累计净值”。“累计净值”不考虑分红给基金净值带来的降低因素，反映了基金成立以来总体的发展情况，而“净值”则是你交易时候的真正价格。 目前国家对个人的基金收益是不收税的。 开放式基金，一般分为股票基金、债券基金、货币基金，以及介于股票和债券基金中间的配置型基金。 有 80% 的基友在决定拿出十万八万元购买基金之前考虑的时间不到半个小时，比买件衣服的时间都少。 美国非常著名的一个基金经理林奇把这种现象称为“Charmin综合征”。Charmin 是美国宝洁公司出的一种卫生纸，几乎在美国任何一个超市里面都可以看见。林奇说：“很多人在买宝洁公司股票前花的时间还不如花在挑 Charmin 卫生纸上的时间多。”这就是“Charmin综合征”。 稀里糊涂、懵懵懂懂地就把大把的钞票投入到一个未知的领域，而且还不想花点时间去研究一下。

本篇文章是 D瓜哥 读《算法导论》的读书笔记。记录下来是为了方便整理思路，以便啃下“动态规划”这块骨头。 目前侧重记录书中关于“动态规划原理”的介绍。接下来会把书中的例子结合 Java 代码演绎一遍。后续会根据D瓜哥的学习和理解，逐步完善。最终希望达到通过这一篇文章，就能学会、理解动态规划。 山高水远，道阻且长，愿一起努力！ — 2020年01月23日 动态规划（dynamic programming）与分治方法相似，都是通过组合子问题的解来求解原问题（在这里，“programming”指的是一种表格法，并非编写计算机程序）。 分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。 动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。 在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子问题。 动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。 动态规划方法通常用来求解最优化问题（optimization problem）。 设计一个动态规划算法的步骤： 刻画一个最优解的结构特征。 递归地定义最优解的值。 计算最优解的值，通常采用自底向上的方法。 利用计算出的信息构造一个最优解。 算法原理 适合应用动态规划方法求解的最优化问题应该具备的两个要素：最优子结构和子问题重叠。 最优子结构 用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个好线索。 发掘最优子结构性质的通过模式 证明问题最优解的第一个组成部分是做出一个选择。做出这次选择会产生一个或多个待解的子问题。 对于一个给定问题，在其可能的第一步选择中，你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间。 利用“剪切-粘贴”（cut-and-paste）技术证明：作为构造原问题最优解的组成部分，每个子问题的解就是它本身的最优解。证明这一点是利用反证法：假定子问题的解不是其自身的最优解，那么我们就可以从原问题的解中“剪切”掉这些非最优解，将最优解“粘贴”进去，从而得到原问题一个更优的解，这与最初的解是原问题最优解的前提假设锚段。 一个刻画子问题空间的好经验是：保持子问题空间尽可能简单，只在必要时才扩展它。 对于不同问题领域，最优子结构的不同体现在两个方面： 原问题的最优解中涉及多少个子问题，以及 在确定最优解使用哪些子问题时，我们需要考察多少种选择。 可以用子问题的总数和每个子问题需要考察多少种选择这两个因素的乘积来粗略分析动态规划算法的运行时间。 在动态规划方法中，通常自底向上地使用最优子结构。也就是说，首先求得子问题的最优解，然后求原问题的最优解。在求解原问题过程中，我们需要在涉及的子问题中做出选择，选出能得到原问题最优解的子问题。原问题最优解的代价通常就是子问题最优解的代价加上由此次选择直接产生的代价。 能够使用贪心算法的问题也必须具有最优子结构性质。贪心算法和动态规划最大的不同在于，它并不是首先寻找子问题的最优解，然后在其中进行选择，而是首先做出一次“贪心”选择—​在当时（局部）看来最优的选择—​然后求解选出的子问题，从而不必费心求解所有可能相关的子问题。 问题：使用贪心算法和动态规划的界线是什么？什么时候使用贪心？什么时候使用动态规划？ 重叠子问题 适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够“小”，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。 如果递归算法反复求解相关的子问题，则就称为最优化问题具有重叠子问题（overlapping subproblems）性质。 与之相对的，适合用分治算法求解的问题通常在递归的每一步都生成全新的子问题。 动态规划算法通常这样利用重叠子问题性质：对每个子问题求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，每次查表的代价为常量时间。 一个问题是否适合用动态规划求解同事依赖于子问题的无关性和重叠性。两个子问题如果不共享资源，它们就是独立的。而重叠是指两个子问题实际上是同一个子问题，只是作为不同问题的子问题出现而已。 将自顶向下的递归算法（无备忘录）与自底向上的动态规划算法进行比较，后者要高效得多，因为它利用了重叠子问题性质。 重构最优解 从实际考虑，通常将每个子问题所做的选择存在一个表中，这样就不必根据代价来重构这些信息。 备忘 可以保持自顶向下策略，同时达到与自底向上动态规划方法相似的效率。思路就是对自然但低效的递归算法加入备忘机制。维护一个表记录子问题的解，但仍然保持递归算法的控制流程。 带备忘的递归算法为每个子问题维护一个表项来保存它的解。每个表项的初值设为一个特殊值，表示尚未填入子问题的解。当递归调用过程中第一次额遇到子问题时，计算其解，并存入对应表项。随后每次遇到同一个问题，只是简单地查表，返回其解。 一个更通用的备忘方法是使用散列技术，以子问题参数为关键字。 通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会比自顶向下备忘算法快，因为自底向上算法没有递归调用的开销，表的维护开销也更小。而且，对于某些问题，可以利用表的访问模式来进一步降低时空代价。相反，如果子问题空间中的某些子问题完全不必求解，备忘方法就会体现出优势了，因为它只会求解那些绝对必要的子问题。 参考资料 算法导论（原书第3版） Dynamic Programming vs Divide-and-Conquer - ITNEXT How to Solve Any Dynamic Programming Problem - Pramp Blog | Coding Interview & Job Search Resources for Developers

D瓜哥在 “告别 2019，迎接 2020” 中已经提过，今年的一个重要改进就是把书读透，学以致用，不求速度但求质量。并且，还提到要重读《如何阅读一本书》和《如何有效阅读一本书》，以求提高读书技能，把书读透。 最近在读《如何阅读一本书》，大概读了五分之一。最近有个想法，何不用《如何阅读一本书》中介绍的方法来阅读《如何阅读一本书》呢？熟悉编程（尤其是 Ruby）的朋友估计该会心一笑，有点元编程的感觉。 D瓜哥这里先大概介绍一下书中的内容，然后再根据读书方法来剖析这本书。 作者在全书第一章就开宗明义地写道：这本书为那些想把读书的主要目的当作是增进理解能力的人而写。 我们的目标就是：第一提醒读者，阅读可以是一件多少主动的事。第二要指出的是，阅读越主动，效果越好。 阅读艺术是一个凭借着头脑运作，除了玩味读物中的一些字句之外，不假任何外助，以一己之力来提升自我的过程。 蒙田说：“初学者的无知在于未学，而学者的无知在于学后。” 阅读的艺术包括了所有非辅助型自我发现学习的技巧：敏锐的观察、灵敏可靠的记忆、想象的空间，再者当然就是训练有素的分析、省思能力。 要避免这样的错误 —— 以为读得多就是读得好的错误。 做一个自我要求的读者 主动阅读的核心就是：你在阅读时要提出问题来 — 在阅读的过程中，你自己必须尝试去回答的问题。 四个基本问题 一个阅读者要提出的四个基本问题: 整体来说，这本书到底在谈些什么？你一定要想办法找出这本书的主题，作者如何依次发展这个主题，如何逐步从核心主题分解出从属的关键议题来。 作者细部说了什么，怎么说的？你一定要想办法找出主要的想法、声明与论点。这些组合成作者想要传达的特殊讯息。 这本书说得有道理吗？是全部有道理，还是部分有道理？ 这本书跟你有什么关系？ 做笔记的方法 画底线 —— 在主要的重点，或重要又有力量的句子下画线。 在画底线处的栏外再加画一道线。 在空白处做星号或其他符号 —— 要慎用。 在空白处编号 —— 作者的某个论点发展出一连串的重要陈述时，可以做顺序编号。 在空白处记下其他的页码 —— 强调作者在书中其他部分也有过同样的论点，或相关的要点，或是与此处观点不同的地方。 将关键字或句子圈出来 —— 这跟画底线是同样的功能。 在书页的空白处做笔记 —— 在阅读某一章节时，你可能会有些问题 （ 或答案 ），在空白处记下来，这样可以帮你回想起你的问题或答案。 . 三种笔记 笔记主要的重点是全书的架构，而不是内容 —— 至少不是细节。因此我们称这样的笔记为结构笔记（Structural Note-making）。 概念笔记（Conceptual Note-making）。 针对一场讨论情境的笔记 —— 辩证笔记 （ Dialectical Note-making）。 你在做这件事时，每一个分开来的步骤都需要你全神贯注地去做。在你分别练习过这些分开来的步骤后，你不但能放下你的注意力，很有效地将每个步骤做好，还能将所有的动作结合起来，表现出一个整体的顺畅行动。 一个人只要学习过一种复杂的技巧，就会知道要学习一项新技巧，一开始的复杂过程是不足为惧的。等所有分开的动作不再分离，渐渐融为一体时，学习者便能将注意力转移到目标上，而他也具备了要达成目标的能力了。 阅读的四个层次 第一层次的阅读为基础阅读（Elementary Reading）。这个层次的任务就是识文认字。 第二层次的阅读为检视阅读（Inspectional Reading）。特点在强调时间。在这个阅读层次，学生必须在规定的时间内完成一项阅读的功课。在一定的时间之内，抓出一本书的重点。检视阅读是系统化略读 （Skimming Systematically） 的一门艺术。

我的 2019 在 2018 年底，我写了 “2019 年度计划” 对 2019 年做了一个简单的规划。2019 年如白驹过隙，稍纵即逝。又到一年年底，现在对这一年做一个总结。 虽然这一年，我一直在意有这么一个计划，但是从来没有认真总结反思过。为了回顾一下，刚刚又打开计划去看，生活才发现过得如此苍白无力。抛开计划，按时间顺序，从头到尾，随意来说吧。 读书 今年读了几本书： 《小岛经济学》 《小王子（英文版）》 《未来世界的幸存者》 《白夜行》 《教父》 《远见》 《如何阅读一本书？》 《文明之光（第一册）》 《基督山伯爵》 《Kubernetes in Action》 《富爸爸穷爸爸》 《巴菲特与索罗斯的投资习惯》 《幸福的方法》 《魔鬼聊天术》 《拆掉思维里的墙》 挑选几本来简单说说吧。 《小岛经济学》 《小岛经济学》是今年读完的第一本书，也算是去年留下的一个尾巴。奥地利经济学派主张政府不干预的观点。这本书简单描述了经济发展的过程，从莽荒时代，手工作业开始，逐步引入工具，提高生产力；随着生产力的提升，人口的增多，经济活动增多，开始物物交换；从物物交换过渡到货币交易，然后银行业兴起；生产力再次提高，以及货币的增加，投资也成为必要，资本市场应运而生；随着地区优势的凸显，资源整合也势在必行，接着发展起了跨国贸易，换汇成为必要，汇率也就被引入进来；随着资本市场的繁荣，埋藏的地雷被引爆，通货膨胀，货币贬值，资本市场崩溃，社会进入大萧条，然后重置继续发展…… 整个过程完整而清晰，犹如亲历过去发展的波澜壮阔。作为一本经济学入门教程还是很赞的。最近开始看曼昆的《经济学原理》，再来看这本书，真的只能是入门。也许智商不够用，也许对经济学的知识了解得过于浅薄，当经济发展到引入汇率之后，后面的发展过程理解的就不是很透彻了。等看一下金融的书，结合起来，希望能更好地理解。 《未来世界的幸存者》 在年初看完的这本书，看完后震撼很大。把当时的读后感直接贴到这里作为总结吧。 作者站在一个技术人员的角度，去思考技术如何改变世界？未来会是什么样子？ 作者的思考和我的思考结果是一样的： 技术的快速发展，机器必定完成大部分重复性劳动，使得大部分劳动者被取代。 大部分人必定只能找到低端工作，工资仅够温饱。 贫富分化将越来越严重，而且会世袭，穷人毫无翻身的可能。 科技发展的结果，我自己感觉是喜忧参半： 作为一名IT从业者，真正在用技术改变这个世界，带给大家更多的便利，这是百年难得一遇的机遇，生在这个伟大的时代，能参与这个伟大的浪潮之中，可以用自己的双手去推动世界的改变，何其幸哉！ 同时，技术带给人们的便利真是难以想象，足不出户点餐、购物、约车、娱乐… 但是，也有很多人是不幸的，他们没有一技之长，或者人到中年，却惨遭失业；还有一部分人，或者说大部分生活在底层的人们，因为没有一技之长（仅指不容易被技术取代的技能），也许永无翻身之日，无所事事，惶惶终日。 技术的发展，造成人类事业，伴随而来的可能会是“黑镜第一季第二集”的样子：每人一张床，四周都是显示器，想看什么看什么，什么活也不用干，平时运动挣积分，拿积分再消费… 进一步发展，也许就是《西部世界》，尤其是娱乐业。 人类本身很可能会再进化一步：进化成碳基+硅基的组合体。碳基就是目前的人（也许仅仅只需要保留大脑），硅基就是各种芯片+维持大脑活动的必要设备和机械躯体… 基因改造将带来彻底的不平衡：人类被分为被改造人和原始人。 《远见》 这本书是在刷知乎时，别人推荐的书。就找来看了看。真是相见恨晚！如果在大学毕业时就看到这本书，也许…… 简单做个摘录作为总结吧。 本书讲人生的职业生涯分为三个阶段： 第一阶段是强势开局的时候。你在职业上的努力必须着重于为前方的漫长道路挖掘和装备自己。你的学习曲线要比职位、职称更加重要。在这一阶段，要为职业生涯打好基础并建立起良好的早期习惯。 第二阶段是聚焦长板的时候。该阶段的首要目标是寻找自己的甜蜜区，即你所擅长的、所热爱的和这个世界所需要的这三者之间的交集。这个时候你要展现自我，让自己鹤立鸡群，想方设法平稳地走在那条收获最大的职场路径上。你要专注于自己的长板，且大可忽略自己的短板。 第三阶段致力于实现持续的影响力，以及寻找一条可以稳定延续到60多岁甚至70多岁的新的可持续职业道路。你要在第三阶段完成三个关键任务：完成继任计划、保持关联性，以及为自己点燃一团新的职业之火。 用一句话来总结：第一阶段：加添燃料，强势开局； 第二阶段：聚焦长板，达到高点； 第三阶段：优化长尾，持续发挥影响力。 三大职场燃料来源：可迁移技能、有意义的经验和持久的关系。 5个数字，树立正确的职场思维 职业生涯的长度：用62减去你目前的年龄。 精通一项技能所需的时间：要花多少小时才能在某一方面达到“精通”？ 40岁之后能赚到的个人财富百分比：在40岁之后，你赚到的钱会占你一生个人财富的百分之多少？大部分人的估计是60%。 社交货币：你有多少社交网络好友？ 职场支持者的人数：你认为能在“职业生涯的天堂”里遇到多少人，也就是说有多少人能对你的职业生涯和人生带来真正的变化？ 这本书的摘要已经发布出来，感兴趣的小伙伴请移步： 《远见》之读书笔记。