首页 > 其他分享 >动态规划问题总结

动态规划问题总结

时间:2022-12-20 10:47:30浏览次数:66  
标签:总结 遍历 递归 数组 动态 规划 dp

动态规划题型难点

  1. 首先找不到dp的规律是什么
  2. 不知道什么时候开始,什么时候结束
  3. 不知道该用遍历还是递归(这个其实两个都一样,只是看个人更喜欢用那一种)

挨个解决

  1. 首先对于找不到dp规律的,其实无非就那几种。后一个是在前一个或者前几个当中取最小/最大值,然后就可以得出类似这样的,dp[i] = Math.max(dp[i - 1]+条件, dp[i - 2] + 条件.....)+条件。基本上动态规划类型的题都素这样,然后知道大概规律了,接下来就是去做题然后巩固一下。
    509.斐波那契数
    1137. 第 N 个泰波那契数
    70. 爬楼梯
    198. 打家劫舍

  2. 不知道什么时候开始,什么时候结束。
    对于这个问题我个人的解决方案就是在题型中分析,比如第198题打家劫舍中,小偷不能连续偷两家挨到的,也就是说从第一二层记录,从第三层开始,因为第一层或者第二层是可以一次就偷到,接下来就需要看第三层去判断dp[2] = Math.max(dp[0] + num[2], dp[1])。所以你懂了吗?(不懂就肯定是题没刷够,hxd,建议多刷几套题,题感就出来了)

3.遍历和递归
在动态规划的问题当中,我做多了题的感觉就是,当你可以只用数组去解决这个题,那么只需要遍历,将结果数组遍历一遍就得行了。但是当你使用数组不能解决这个问题的时候,可能就需要去使用递归然后进行判断或者是其他的一些操作去辅助遍历数组。

标签:总结,遍历,递归,数组,动态,规划,dp
From: https://www.cnblogs.com/taosifan/p/15358905.html

相关文章

  • 测试工程师要如何规划自己的职业生涯?
    本文首发自「慕课网」,想了解更多IT干货内容,程序员圈内热闻,欢迎关注!作者|慕课网精英讲师陈磊想要成为一名合格的测试工程师并不是一件容易的事情,但是想要划水的人生其实也......
  • 基于 Dubbo Admin 动态进行流量隔离
    Dubbo提供动态流量隔离的服务治理能力,可以在无需重启应用的情况下,动态进行流量隔离。Dubbo可以通过XML配置,注解配置,动态配置实现流量隔离,这里主要介绍动态配置的方式,其他......
  • 高可用系列文章之四 - 总结
    前文链接高可用系列文章之一-概述-东风微鸣技术博客(ewhisper.cn)高可用系列文章之二-传统分层架构技术方案-东风微鸣技术博客(ewhisper.cn)高可用系列文章......
  • 一天作息学习方法总结
    睡前静态冥想,降低脑活动。意念冥想,专注聚焦有意义&熟悉的事情,复习提升,摒除杂念。放空思想,控制自己放空思想。少量运动,适量小运动,产生乏力感。具象化杂念,解决掉,不再多......
  • 动态库的重复链接
    动态库的重复链接背景如果现有系统的库有两个层次,底层库和接口库。接口库通过dlopen的方式加载底层库,接口库提供给用户使用。现在需要在用户层调用底层库的接口,应该如何......
  • Spring Security 动态url权限控制
    一、前言本篇文章将讲述SpringSecurity动态分配url权限,未登录权限控制,登录过后根据登录用户角色授予访问url权限基本环境 spring-boot2.1.8mybatis-plus2.2.0......
  • [论文总结] 石榴综述论文阅读笔记
    date:2020-12-0721:19:18+0800tag:-论文总结1.石榴汁作为功能食品;有关其多酚,治疗优点和最新专利的全面综述1.1内容论文从多个方面介绍了石榴汁的功能药效,......
  • [论文总结] 森林管理和造林业中复杂观念的转变
    date:2020-12-0721:04:57+0800tag:-论文总结森林管理和造林业中复杂观念的转变[参考论文]Shiftingconceptionsofcomplexityinforestmanagementandsilv......
  • [论文总结] 美国造林业:过去30年的惊人变化时期
    date:2020-12-0721:02:24+0800tag:-论文总结论文.Anthonyetal.,JournalofForestry,Volume116,Issue1,January2018,Pages55–67.前言1986年,《林......
  • [论文总结] 均匀和不均匀造林对生态多样性的影响综述
    date:2020-12-0720:57:54+0800tags:论文总结1.介绍文章介绍了森林经营的现状和问题,以及解释了均匀年龄造林和非均匀年龄造林的区别。均匀年龄造林有利于以多数......