动态规划法(一)——概述

什么是动态规划法

动态规划法也是用于求解最优化问题,也采用分步决策的策略,将一个大问题划分成若干个较小的同类子问题,根据子问题的解,自底向上,得出整个问题的解。

与贪心法的异同

相同

  1. 都是用于求解最优化问题;
  2. 都采用分步决策,计算出每一步的最优解。

不同

  1. 贪心法的每一步决策依赖于『最优量度标准』,不依赖于子问题的解和尚未作出的选择;
  2. 动态规划法每一步决策依赖于子问题的解,无需最优量度标准。

与分治法的异同

相同

  1. 都将问题话分成若干个规模较小的同类型子问题。

不同

  1. 分治法会有重叠子问题的现象,对于一些子问题会重复计算,而动态规划法能避免重叠子问题现象。

最优子结构

动态规划法具有最优子结构特性。 最优子结构特性:一个问题的最优解包含其子问题的最优解。 当一个问题具有最优子结构特性时,在构造该问题最优解的过程中,只需考虑每一个子问题的最优解。因为每个子问题的最优解构成了该问题的最优解。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏拭心的安卓进阶之路

Java 集合深入理解(6):AbstractList

今天心情比天蓝,来学学 AbstractList 吧! ? 什么是 AbstractList ? AbstractList 继承自 AbstractCollec...

19210
来自专栏alexqdjay

HashMap 多线程下死循环分析及JDK8修复

1K4
来自专栏xingoo, 一个梦想做发明家的程序员

Spark踩坑——java.lang.AbstractMethodError

百度了一下说是版本不一致导致的。于是重新检查各个jar包,发现spark-sql-kafka的版本是2.2,而spark的版本是2.3,修改spark-sql-...

1210
来自专栏Java Edge

AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

462
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-向量实现《数据结构与算法分析》

#include <iostream> #include <list> #include <string> #include <vector> #include...

1736
来自专栏开发与安全

算法:AOV网(Activity on Vextex Network)与拓扑排序

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称之为AOV网(Activity on Vextex ...

2607
来自专栏ml

朴素贝叶斯分类器(离散型)算法实现(一)

1. 贝叶斯定理:        (1)   P(A^B) = P(A|B)P(B) = P(B|A)P(A)   由(1)得    P(A|B) = P(B|...

3467
来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

1762
来自专栏xingoo, 一个梦想做发明家的程序员

AOE关键路径

这个算法来求关键路径,其实就是利用拓扑排序,首先求出,每个节点最晚开始时间,再倒退求每个最早开始的时间。 从而算出活动最早开始的时间和最晚开始的时间,如果这两个...

2527
来自专栏计算机视觉与深度学习基础

Leetcode 114 Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, Given...

1958

扫码关注云+社区