dp(动态规划) |
您所在的位置:网站首页 › 01规划问题能用excel求解吗 › dp(动态规划) |
动态规划(英语:Dynamic programming,简称 DP),是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems 以上定义来自维基百科,看定义感觉还是有点抽象。简单来说,动态规划其实就是,给定一个问题,我们把它拆成一个个子问题,直到子问题可以直接解决。然后呢,把子问题答案保存起来,以减少重复计算。再根据子问题答案反推,得出原问题解的一种方法。 一般这些子问题很相似,可以通过函数关系式递推出来。然后呢,动态规划就致力于解决每个子问题一次,减少重复计算,比如斐波那契数列就可以看做入门级的经典动态规划问题。 动态规划核心思想动态规划最核心的思想,就在于拆分子问题,记住过往,减少重复计算。 我们来看下,网上比较流行的一个例子: A : “1+1+1+1+1+1+1+1 =?” A : “上面等式的值是多少” B : 计算 “8” A : 在上面等式的左边写上 “1+” 呢? A : “此时等式的值为多少” B : 很快得出答案 “9” A : “你怎么这么快就知道答案了” A : “只要在8的基础上加1就行了” A : “所以你不用重新计算,因为你记住了第一个等式的值为8!动态规划算法也可以说是 ‘记住求过的解来节省时间’” |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |