动态规划 动态规划（英语：Dynamic programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方...
IP属地：湖南
-
快速入门动态规划（背包问题、硬币找零问题、编辑距离问题、最长上升子序列问题、最长公共子序列问题、旅行商问题） -
算法设计与分析笔记之NP完备性理论一. P、NP、NPC 三类问题都会涉及到多项式时间算法，我们先解决什么是多项式时间算法。 多项式时间的算法的形式化定义是，对于规模为n的输入，在最坏情况下的运行时间是...
-
算法设计与分析笔记之最大流/最小割问题割（Cut） s-t cut：(A, B)，将图分为两部分A和B，源s∈A，终点t∈Bcut(A, B)的容量（capacity）：所有流出A的边的容量和，注意区分与流量（f...
-
-
最长公共子序列（LCS）——动态规划问题描述 子序列是指，从序列中选出一些子元素，需满足其前后关系与在原序列中相同；公共是指该序列同时是两个序列的子序列。如两个序列{4，2，1 ，6，5，8，13，18，9...
-
硬币找零问题——动态规划
问题阐述 给定一些面值的硬币（数量不限）和需要找零的金额，求一个找零所需硬币数最少的方案。现实生活中因其面值的特殊性，我们往往采用贪心策略，即每次选取满足条件的面值最大的硬币...
-
背包问题之0-1背包
背包问题是典型的动态规划例子。我们可将子问题的解存储下来，以免计算其母问题时需用到子问题结果而重复计算。 问题阐述 给定背包容量W，n个物品及各个物品的价值和重量，问如何选择...
-
