千恋*万花

  • 首页
  • 个人简历
  • 文章分类
    • 后端开发
    • 运维
    • 基础知识
    • 笔记
    • 工作运维记录
    • 随笔
    • 未分类文章
  • 管理
    • 后台管理
    • 登出
萌奈の笔记簿
分享我的努力,希望为你助力
  1. 首页
  2. 基础知识
  3. 算法与数据结构
  4. 正文

动态规划解题大纲

2022-11-01 656点热度 0人点赞 0条评论

思考方向

对于动态规划的题,可以分为五步去思考:

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

入门题目《斐波那契数列》

  1. 确定dp数组以及下标的含义
    dp[i] = 第 i 个斐波那契数的值

  2. 确定递推公式
    斐波那契数的定义即为递推公式,即 dp[i] = dp[i-1] + dp[i-2]

  3. dp数组如何初始化
    斐波那契数已经假设 dp[0] = 0; dp[1] = 1

  4. 遍历顺序
    由递推公式可知,若要求解 dp[i] 需要先知道 dp[i-1] 和 dp[i-2] 的值
    所以遍历顺序应该为 从前往后

  5. 举例推导dp数组(重要)
    根据定义,自己先在纸上算出斐波那契数列的前几个值。
    随后编写程序,用程序求解得到dp数组,打印dp数组,检查dp数组是否与自己的预期值是否有偏差。
    当发现自己的程序有错误无法AC时,可以通过第五步来Debug程序,以确认是第几步出现了问题

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2022-11-01

初音萌奈

我是练习时长 一年半 的后端开发程序员 谢谢你参观我的博客! 本网站现已支持IPv6 ☞ 个人简历 ☜

点赞
< 上一篇
下一篇 >

文章评论

取消回复
文章目录
  • 思考方向
  • 入门题目《斐波那契数列》

COPYRIGHT © 2023 HatsuneMona ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

晋ICP备17007130号-4