什么是动态规划?

原文链接:https://note.noxussj.top/?source=helloworld


什么是动态规划?

动态规划也是算法设计的一种方法/思想。它将一个问题分解为相互重叠的子问题,通过反复求解子问题,来解决原来的问题。

基础案例

场景一

斐波那契数列

当前数等于前面两个数的和。

img

定义子问题:f(n) = f(n-1) + f(n-2)

点赞
收藏

评论区

加载中...

相关推荐

Oracle 分组与拼接字符串同时使用

SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(

初步了解01背包问题(分治篇)

目录问题描述(问题描述)输入格式(输入格式)输出格式(输出格式)基于0/1背包的迭代算法(基于01背包的动态规划算法)0/1背包问题的分析(01背包问题的分析)分治法(分治法)总结(总结)问题描述Coda非常喜欢玩“NewWorldOnline”,受到某部动画的影响,他

基于01背包问题的动态规划算法

目录初步认识动态规划(初步认识动态规划)与动态规划有关的理论知识:(与动态规划有关的理论知识:)动态规划中的最优决策表(基于填表的动态规划算法)最终版动态规划(最终版动态规划)总结(总结:)初步认识动态规划动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推

【分治法】解决中位数问题、格雷码问题以及分治法直接折半存在的问题讨论————武汉理工大学算法分析实验1

AlgorithmExperiment算法分析课实验分治法的核心思想是将问题分为若干子问题去,使规模一步步缩小,最终分到一步就能得出结果。要注意每个子问题需要性质相同而且相互不重复。采用分治法完成如下任务:i.中位数问题问题描述设X0:n1和Y0:n–1为两个数组,每个数组中含有n个已排好序的数。找出X和Y

Java面试不得不知的程序(二)

【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?斐波那契数列:前面相邻两项之和,构成了后一项通项公式注:此时a11,a21,ana(n1)a(n2)(n3,n∈N\)通项公式的推导斐波那契数列:1、1

Python递归函数、匿名函数、过滤函数

递归函数Python对递归的深度有限制,超过即会报错。所以一定一要注意跳出条件。斐波拉契数列一个数列,第一个数是1,第二个数也是1,从第三个数开始,每一个数是前两个数之和公式:f(1)1,f(2)1,f(3)f(1)f(2),...,f(n)f(n2)f(n1)