3.8 0-1背包问题(Knapsack problem)3.8.1 问题描述其中每种物品只有1件，存放哪些物品，才能使背包存放物品价值最高？ 3.8.2 算法思路假设背包空间只有1kg、2kg...

3.7 矩阵连乘(Matrix chain multiplication)3.7.1 问题描述求多个矩阵连乘的最优次序，使得所需的乘法次数最少，并求出所需的乘法次数。 3.7.2 算法思路跟以往...

3.6 最短路径3.6.1 问题描述最短路径问题(Shortest path problem)：再不回退的前提下，找到A到F的最短路径 3.6.2 算法思路A到B1的最短路径为4，前序节点为A；...

3.5 最长公共子序列(LCS)3.5.1 问题描述最长公共子序列(Longest Common Subseuence，LCS)问题：给定两个字符串，求解它们的最长公共子序列的长度，其中子序列是...

3.4 切木材问题(Rod-cutting problem)3.4.1 问题描述给一个长度为17的木材，可以切成小段卖出，价格根据小段的长度不同而不同。如何通过切成小段卖出尽可能高的总价钱？ 3...

3.3 跳跃问题(Jump Game)3.3.1 问题描述给定一个非负整数数组，初始状态你在数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。请判断，你最后是否能够抵达最后一个...

3 动态规划(Dynamic Programming)3.1 算法介绍3.1.1 动态规划特性 问题分阶段：一个问题的求解可以拆分成若干个阶段的子问题 阶段有依赖：问题的最优解依赖于子阶段问题...

2.9 二维最近点对问题2.9.1 问题描述问题描述：二维平面上有n个点，如何找到距离最近的点？ 2.9.2 暴力求解1 算法思路二维平面上有n个点，则有(n-1)+(n-1)+...+1=n(...

2.8 赛程安排2.8.1 问题描述n(n=2k)个选手参赛，设计一个满足以下要求的比赛日程表： 每个选手必须与其他n-1个选手各比赛一次； 每个选手一天只能比赛一次； 循环赛一共进行n-1天...

2.7 寻找第K最小数2.7.1 算法思路整体思路：结合2.6节的快速排序 如果基准位就是第k位，就直接返回 如果基准位在k的左端，就从基准位到尾部找 如果基准位在k的右端，就从首部到基准位找...