漫画：5分钟了解什么是动态规划？
作者 | 调皮的阿广
来源 | 视学算法（ID：z872561826）
动态规划，英文是Dynamic Programming，简称DP，擅长解决“多阶段决策问题”，利用各个阶段阶段的递推关系，逐个确定每个阶段的最优决策，并最终得到原问题的最优决策。
注意：动态规划往往使用表格来存储中间结果
注意：每一步上几层台阶，都是一个决策问题！
说到这里，阿广你有没有发现几点问题？
1、将求F（10）这个问题，完美的分解成了F（9）和F（8），找到了局部的最优解，与贪心算法有点像呀。
2、既然F（10）=F（9）+F（8），那么F（9）=F（8）+F（7），依此类推，最终问题被逐渐降低了规模，越来越简单，这也是分治算法的思想。
动态规划的三要素：
1、最优子问题
F（10）=F（9）+F（8），就是F（10）问题的最优子问题，局部的贪心完美的将问题分解，如果得到的F（9）和F（8）都是最优解，那么F（10）一定也是最优解了。
2、边界条件
分解到最后，一定是变成了规模最简单的问题，即F（1）和F（2），这两个问题不能再分解了，不过没关系，他们很简单，用你的小心心算就ok了。
3、状态转移方程（DP方程）
本问题的状态转移方程为：F（n）=F(n-1)+F(n-2)，这就是解决问题的核心，使得状态能够“动”起来。
注意：相同颜色的部分代表相同的结果
可以看出来，动态规划算法的核心是DP方程。
所以说，状态转换方程（DP方程）就是算法的核心，那么设计DP方程，要有什么注意的呢？以下列出来几点！
1、最优化子问题
从上面的算法三要素中，可以看出，DP方程是最优子问题中归纳而来的。那么，什么才算“最优子问题”呢？就是说，不管之前决策是否是最优决策，都必须保证从现在开始的决策是在之前的基础上最优。具体的说，我们默认F（8）和F（9）就是最优的，在此基础上，得到最优的F（10）。
2、不影响后续决策
由于上一条我们看到，如果F（8）的决策会影响到F（9）和F（10）的决策，那么F（10）=F（9）+F（8）就不成立了，所以，要一定保证，每个阶段的决策仅受之前决策的影响，但不影响之后阶段的决策。
典型应用1---01背包问题
01背包问题的决策，就是判断第i件物品，装还是不装，哪种决策总价值最大？
那么，我们是否能够定义状态为s[i]呢，用来表示第i件物品决策的最大价值？
答案是不可以的，因为这个状态会影响到后面的决策，换种说法讲，装不装入一个物品，会影响到背包中的剩余空间，所以后面的决策当然会受影响。
典型应用2---最长公共子序列问题（这一问题常被用于比较“相似度”）
决策方式就是判断str1[i]和str2[j]的关系，关系不同，则DP方程不同。
原文链接：
https://mp.weixin.qq.com/s/-bngVVU3O1HaXJDnLYbUgg
(*本文为 AI科技大本营转载文章，转载请联系作者)
◆
福利时刻
◆
入群参与每周抽奖~
扫码添加小助手，回复：大会，加入福利群，参与抽奖送礼！
AI ProCon 2019 邀请到了亚马逊首席科学家@李沐，在大会的前一天（9.5）亲授「深度学习实训营」，通过动手实操，帮助开发者全面了解深度学习的基础知识和开发技巧。还有 9大技术论坛、60+主题分享，百余家企业、千余名开发者共同相约 2019 AI ProCon！5折优惠票抢购中！
推荐阅读
每天超50亿推广流量、3亿商品展现，阿里妈妈的推荐技术有多牛
面向可解释的NLP：北大、哈工大等提出文本分类的生成性解释框架
物联网将如何影响你的钱包？
写爬虫，怎么可以不会正则呢？
白话中台战略：中台是个什么鬼？
零基础如何自学编程？| 程序员有话说
送50本 Python、数据库、java方面的书，包邮给你！！
鸿蒙霸榜 GitHub，从最初的 Plan B 到“取代 Android”？
9012年了，我不允许你还不会玩 IPFS!
你点的每个“在看”，我都认真当成了喜欢
相关文章：
小程序大转盘红包雨营销组件
前言 商城没几个营销活动能叫商城吗？所以就来几个组件吧，写的不好轻踩，对你有帮助记得给个小星星哦直接上链接github链接 运行例子 git clone https://github.com/sunnie1992/soul-weapp.git 微信开发者工具打开项目 营销组件 大转盘 "p…
Windows Server 2012 RDS系列：虚拟桌面化（5）
概述：本次将系列地测试Windows Server 2012 远程桌面服务（RDS），将过程进行分享，总的感觉比2008 R2更简单了，体现着2012的自动化。2012的RDS部署有标准部署和快速启动两种，快速启动就是自动快速配…
里程碑式成果Faster RCNN复现难？我们试了一下 | 附完整代码
作者 | 已退逼乎 来源 | 知乎【导读】2019年以来，除各AI 大厂私有网络范围外，MaskRCNN，CascadeRCNN 成为了支撑很多业务得以开展的基础，而以 Faster RCNN 为基础去复现其他的检测网络既省时又省力，也算得上是里程碑性成…
【跃迁之路】【725天】程序员高效学习方法论探索系列（实验阶段482-2019.2.15）...
实验说明 从2017.10.6起，开启这个系列，目标只有一个：探索新的学习方法，实现跃迁式成长实验期2年（2017.10.06 - 2019.10.06）我将以自己为实验对象。我将开源我的学习方法，方法不断更新迭代&#…
C/C++各种数据类型转换汇总
以下是Windows/Linux系统中常用的C/C各种数据类型转换汇总：#ifndef FBC_MESSY_TEST_DATA_TYPE_CONVERT_HPP_ #define FBC_MESSY_TEST_DATA_TYPE_CONVERT_HPP_#include <stdio.h> #include <stdlib.h> #include <iostream> #include <string>…
ASP.NET技巧：两个截取字符串的实用方法
两个截取字符串的实用方法（超过一定长度自动换行）1/** <summary> 2 /// 截取字符串，不限制字符串长度 3 /// </summary> 4 /// <param name"str">待截取的字符串</param> 5 /…
吃瓜腾讯平均月薪7.27万后，微信又出大招
腾讯最新财报一出，喜提热搜！据腾讯第二季度财报显示：2019 年上半年腾讯有员工56310人，总薪酬成本为242.59亿元，腾讯员工平均半年薪为43.08万元。在第一季度里，腾讯员工平均季度薪资为21.27万元，…
回调函数在C/C++中的使用
回调函数就是一个通过函数指针调用的函数。假如把A函数的指针当作参数传给B函数,然后在B函数中通过A函数传进来的这个指针调用A函数，那么就是回调机制。A函数就是回调函数，而通常情况下，A函数是在系统符合你设定的条件下自动执行。使用回调函…
excel单元格加引号及逗号，转换为sql需要的样式
A1 B1BXQY001 ------> BXQY001,BXQY001 -----> BXQY001 在B1中输入公式： ""&A1&""&"," 在B2中输入公式： ""&A1&"" 去掉了后面的逗号。其实就是 " "&A1&…
Win7/Win8 系统下安装Oracle 10g 提示“程序异常终止，发生未知错误”的解决方法...
我的Oracle 10g版本是10.2.0.1.0，（10.1同理）选择高级安装，提示“程序异常终止，发生未知错误”。1.修改Oracle 10G\database\stage\prereq\db\refhost.xml当打开refhost.xml 后会发现有</SYSTEM> <CERTIFIED…
Caffe基础介绍
Caffe的全称应该是Convolutional Architecture for Fast Feature Embedding，它是一个清晰、高效的深度学习框架，它是开源的，核心语言是C，它支持命令行、Python和Matlab接口，它既可以在CPU上运行也可以在GPU上运行。它的…
飞桨博士会第三期来啦！中国深度学习技术俱乐部诚邀您加入
飞桨博士会是由百度开源深度学习平台飞桨（PaddlePaddle）发起的中国深度学习技术俱乐部，旨在打造深度学习核心开发者交流圈，助力会员拓展行业高端人脉、交流前沿技术。俱乐部为会员制，成员皆为博士生导师或博士…
canvas 拼图
效果 代码 <!DOCTYPE html> <html lang"zh_CN"> <head><meta charset"UTF-8"><title>拼图</title><script src"https://code.jquery.com/jquery-3.3.1.js"></script> </head> <body&g…
性能优化之Java(Android)代码优化
最新最准确内容建议直接访问原文：性能优化之Java(Android)代码优化 本文为Android性能优化的第三篇——Java(Android)代码优化。主要介绍Java代码中性能优化方式及网络优化，包括缓存、异步、延迟、数据存储、算法、JNI、逻辑等优化方式。(时间仓促&#…
1小时上手MaskRCNN·Keras开源实战 | 深度应用
作者 | 小宋是呢来源 | CSDN博客0. 前言介绍开源地址：https://github.com/matterport/Mask_RCNN个人主页：http://www.yansongsong.cn/MaskRCNN 是何恺明基于以往的 faster rcnn 架构提出的新的卷积网络，一举完成了 object instance segmentat…
MNIST数据库介绍及转换
MNIST数据库介绍：MNIST是一个手写数字数据库，它有60000个训练样本集和10000个测试样本集。它是NIST数据库的一个子集。MNIST数据库官方网址为：http://yann.lecun.com/exdb/mnist/ ，也可以在windows下直接下载，train-im…
PostgreSQL学习笔记(1)
安装psql brew install postgresql 启动服务 brew services start postgresql 使用psql进入控制台，报错： psql: FATAL: database "<user>" does not exist 看来是没有给我的当前用户创建数据库，使用下面命令进入名为templat…
怎样使一个Android应用不被杀死？（整理）
2019独角兽企业重金招聘Python工程师标准>>> 方法 ： 对于一个service，可以首先把它设为在前台运行： public void MyService.onCreate() { super.onCreate(); Notification notification new Notification(android.R.drawable.my_…
Ubuntu 14.04 64位机上用Caffe+MNIST训练Lenet网络操作步骤
1. 将终端定位到Caffe根目录； 2. 下载MNIST数据库并解压缩：$ ./data/mnist/get_mnist.sh 3. 将其转换成Lmdb数据库格式：$ ./examples/mnist/create_mnist.sh 执行完此shell脚本后，会在./examples/mnist下增加两个新…
IJCAI 2019：中国团队录取论文超三成，北大、南大榜上有名
作者 | 神经小姐姐来源 | HyperAI超神经（ ID: HyperAI )【导读】AI 顶会 IJCAI 2019 已于 8 月 16 日圆满落幕。在连续 7 天的技术盛会中，与会者在工作坊了解了 AI 技术在各个领域的应用场景，聆听了 AI 界前辈的主题演讲，还有机会…
适合小小白的完整建设流程
时常有中小企业建站的客户问到我要自己建网站，应该怎么开始？建站有一定的技术门槛，首先要明白建站要做的哪些事情，里面有哪些坑，把流程弄清楚了才能避免入坑，半途而废！下面总结了建站的流程还有…
ios项目文件结构 目录的整理
2019独角兽企业重金招聘Python工程师标准>>> /<ProjectName>/Shared/Application # App delegate and related files/Controllers # Base view controllers/Models # Models, Core Data schema etc/Views # Shared views/Libr…
重磅！全球首个可视化联邦学习产品与联邦pipeline生产服务上线
【导读】作为全球首个联邦学习工业级技术框架，FATE支持联邦学习架构体系与各种机器学习算法的安全计算，实现了基于同态加密和多方计算（MPC）的安全计算协议，能够帮助多个组织机构在符合数据安全和政府法规前提下&#x…
SpringBoot之集成swagger2
maven配置 <dependency><groupId>io.springfox</groupId><artifactId>springfox-swagger2</artifactId><version>2.5.0</version> </dependency> <dependency><groupId>io.springfox</groupId><artifact…
Windows Caffe中MNIST数据格式转换实现
Caffe源码中src/caffe/caffe/examples/mnist/convert_mnist_data.cpp提供的实现代码并不能直接在Windows下运行，这里在源码的基础上进行了改写，使其可以直接在Windows 64位上直接运行，改写代码如下：#include "stdafx.h"…
关于less在DW中高亮显示问题
首先， 找到DW 安装目录。 Adobe Dreamweaver CS5.5\configuration\DocumentTypes 中的，MMDocumentTypes.xml 这个文件，然后用记事本打开，查找CSS 把 CSS 后边加上，less 然后到。C:\Users\Administrator\AppData\Roamin…
Windows7 64bit VS2013 Caffe train MNIST操作步骤
1. 使用http://blog.csdn.net/fengbingchun/article/details/47905907中生成的Caffe静态库； 2. 使用http://blog.csdn.net/fengbingchun/article/details/49794453中生成的LMDB数据库文件； 3. 新建一个train_mnist控制台工程&#…
NLP机器翻译深度学习实战课程基础 | 深度应用
作者 | 小宋是呢来源 | CSDN博客0.前言深度学习用的有一年多了，最近开始 NLP 自然处理方面的研发。刚好趁着这个机会写一系列 NLP 机器翻译深度学习实战课程。本系列课程将从原理讲解与数据处理深入到如何动手实践与应用部署，将包括以下内容：…
个人站点渲染和跳转过滤功能
核心逻辑：在url里加入正则，匹配分类、标签、年月日和其后面的参数，在视图函数接收这些参数，然后进行过滤。 urls.py # 个人站点的跳转 re_path(r^(?P<username>\w)/(?P<condition>tag|category|archive)/(?P<pa…
三步10分钟搞定数据库版本的降迁 （将后台数据库SQL2008R2降为SQL2005版本）
三步10分钟搞定数据库版本的降迁 （将SQL2008R2降为SQL2005版本）转载原文，并注明出处！虽无多少技术含量，毕竟是作者心血原创，希望理解。转自 http://blog.csdn.net/claro/article/details/6449824前思后想仍…