动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客- | ImapBox

动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客-

31 五月
星期日, 31 五月 2020 03:48 Last Updated on 星期日, 31 五月 2020 03:48 0 Comments

动态规划 

  • 科技公司面试必考算法
  • 题目类型多，没有固定模板
  • 难度属于中上
  • 根据面试经验，一半失败的面试都与动态规划有关
  • 必须掌握
  • 并没有那么可怕
  • 有规律可循
  • 掌握其中的思想，举一反三

什么是动态规划

给定一个矩阵网格，一个机器人从左上角出发，每次可以向下或向右走一步

题A：求有多少种方式走到右下角（动态规划）           题B：输出所有走到右下角的路径（递归，dfs）

               
               
               
               

动态规划题目特点

1.计数

  • 有多少种方式走到右下角
  • 有多少种方式选出k个数使得和是Sum

2.求最大最小值

  • 从左上角走到右下角的路径的最大数字和
  • 最长上升子序列长度

3.求存在性

  • 取石子游戏，先手是否必胜
  • 能不能选出k个数使得和是Sum

例题

lintcode 669；

问题：如何用最少的硬币组合正好付清，不需要对方找钱？

（最值型）动态规划组成部分之一：确定状态

  • 状态在动态规划中的作用属于定海神针
  • 简单的说，解动态规划的时候需要开一个数组，数组的每个元素发f[i]或者f[i][j]代表什么

确定状态需要两个意识：最后一步，子问题

（最值型）动态规划组成部分之二：转移方程

  • 设状态f[x]=最少用多少枚硬币拼出
  • 对于任意x，f[x]=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}

（最值型）动态规划组成部分之三：初始条件和边界情况

  • f[x]=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}
  • 两个问题：x-2，x-5或者x-7<0怎么办？什么时候停下来？
  • 如果拼不出Y，就定义f[y]=正无穷，例如，f[-1].
  • 初始条件：f[0]

（最值型）动态规划组成部分之四：计算顺序

  • 一个原则：当我们计算到f[x]时，f[x-2],f[x-5],f[x-7]都已经得到结果

  • 动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客- 动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客- 1
  • 动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客- 评论
  • 动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客-
    x

    海报

    扫一扫，海报

  • 动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客- 动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客-
  • 动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客- 手机看

    到微信朋友圈

    x

    扫一扫，手机阅读

  • 动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客-打赏

    打赏

    动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客-

    qq_45943739

    “你的鼓励将是我创作的最大动力”

    5C币 10C币 20C币 50C币 100C币 200C币

动态规划入门（九章算法）笔记数据结构与算法qq45943739的博客-



 
 
 
 


本页所有内容来自官方网站 https://www.imapbox.com 新闻来源：互联网搜索引擎和新闻站

本网页所有图片由 ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片，下载并得到。

ImageBox 图片批量下载器 工具地址: 网页图片批量下载工具-最新版本下载

非凡下载站地址：https://www.crsky.com/soft/35838.html

本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。

ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载

本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.




文章目录

  • 全球报导 (16311)
  • 全球云计算 (29506)
  • 程序员专区 (1974)
  • Imap 全球通用标准协议 (7)
  • 全球邮局列表 (17)
  • Imapbox 系列软件 (3)
  • 产品一览 (6)
  • 事业方向 (7)
  • 联系我们 (2)

官方链接

imapbox邮箱网盘 imapbox 海外官网 iMapBox百度百科

登录