算法专题：动态规划

动态规划是[http://zh.wikipedia.org/w/index.php?title=最优化原理&action=edit 最优化原理]中的一种重要的方法。

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存[http://zh.wikipedia.org/w/index.php?title=递归&variant=zh-cn 递归]时的结果，因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决。

• 总的来说，动态规划的优势在于：
• 重叠子问题
• 最优子结构
• 记忆化

步骤

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态 规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表 格中简单地查看一下结果，从而获得较高的效率。

动态规划典型例题

• [http://algorithm.diy.myrice.com/problems/problem_set/guard/problem.htm 皇宫看守]

• [http://algorithm.diy.myrice.com/problems/problem_set/quadrel/problem.htm 方砖问题]

• [http://algorithm.diy.myrice.com/problems/problem_set/hpc/problem.htm 高性能计算机]

• [http://algorithm.diy.myrice.com/problems/problem_set/matrix_chain_mul/problem.htm 计算矩阵连乘积 ]

• [http://algorithm.diy.myrice.com/problems/problem_set/LCS/problem.htm 最长公共子序列]

• [http://algorithm.diy.myrice.com/problems/problem_set/polygon/problem.htm 凸多边形的最优三角剖分 ]

• [http://algorithm.diy.myrice.com/problems/problem_set/bitonic/problem.htm Bitonic旅行路线问题 ]

• [http://algorithm.diy.myrice.com/problems/problem_set/polygon_cal/problem.htm 多边形计算 ]

• [http://algorithm.diy.myrice.com/problems/problem_set/character_recognition/problem.htm 字符识别 ]

• [http://algorithm.diy.myrice.com/problems/problem_set/printing/problem.htm 优美打印 ]

• [http://algorithm.diy.myrice.com/problems/problem_set/edit_distance/problem.htm 编辑距离 ]

• [http://algorithm.diy.myrice.com/problems/problem_set/vitebi/problem.htm Vitebi算法]

• 最长单调子序列
• Floyd-Warshall算法

动态规划练习

Vol I [http://acm.zju.edu.cn/show_problem.php?pid=1013 1013 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1022 1022 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1025 1025 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1027 1027 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1074 1074 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1076 1076 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1093 1093 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1094 1094 by javaman ] Vol II [http://acm.zju.edu.cn/show_problem.php?pid=1100 1100 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1107 1107 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1108 1108 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1136 1136 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=1149 1149 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1183 1183 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1196 1196 by javaman ] Vol III [http://acm.zju.edu.cn/show_problem.php?pid=1200 1200 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1206 1206 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1227 1227 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1234 1234 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1245 1245 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1249 1249 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1250 1250 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1276 1276 by javaman ] Vol IV [http://acm.zju.edu.cn/show_problem.php?pid=1303 1303 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1346 1346 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1353 1353 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1366 1366 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1368 1368 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=1387 1387 by javaman ] Vol V [http://acm.zju.edu.cn/show_problem.php?pid=1424 1424 by SgHao ] [http://acm.zju.edu.cn/show_problem.php?pid=1425 1425 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1428 1428 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1446 1446 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1448 1448 by SgHao ] [http://acm.zju.edu.cn/show_problem.php?pid=1449 1449 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1454 1454 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1459 1459 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1462 1462 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1463 1463 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1470 1470 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1474 1474 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=1475 1475 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1483 1483 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1484 1484 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1490 1490 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=1499 1499 by javaman ] Vol VI [http://acm.zju.edu.cn/show_problem.php?pid=1503 1503 by pandahyx ] [http://acm.zju.edu.cn/show_problem.php?pid=1512 1512 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1515 1515 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1520 1520 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1524 1524 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1539 1539 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1540 1540 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=1554 1554 by SgHao ] [http://acm.zju.edu.cn/show_problem.php?pid=1563 1563 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1567 1567 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=1579 1579 by javaman ] Vol VII [http://acm.zju.edu.cn/show_problem.php?pid=1602 1602 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1607 1607 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1611 1611 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1629 1629 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1638 1638 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1642 1642 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1651 1651 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1666 1666 by Vegetable Bird ] [http://acm.zju.edu.cn/show_problem.php?pid=1695 1695 by caopeng] Vol VIII [http://acm.zju.edu.cn/show_problem.php?pid=1713 1713 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1717 1717 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1731 1731 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1733 1733 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1736 1736 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=1738 1738 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1743 1743 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1756 1756 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1757 1757 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1787 1787 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1792 1792 by javaman ] Vol IX [http://acm.zju.edu.cn/show_problem.php?pid=1800 1800 by SgHao ] [http://acm.zju.edu.cn/show_problem.php?pid=1819 1819 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1853 1853 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1864 1864 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=1877 1877 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1880 1880 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1893 1893 by javaman ] Vol X [http://acm.zju.edu.cn/show_problem.php?pid=1913 1913 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1918 1918 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1925 1925 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1953 1953 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1985 1985 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1986 1986 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1988 1988 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1991 1991 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=1995 1995 by SgHao ] Vol XI [http://acm.zju.edu.cn/show_problem.php?pid=2002 2002 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2014 2014 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2025 2025 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2042 2042 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2058 2058 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2059 2059 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2067 2067 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2068 2068 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2069 2069 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2081 2081 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2096 2096 by javaman ] Vol XII [http://acm.zju.edu.cn/show_problem.php?pid=2127 2127 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2136 2136 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2142 2142 by SgHao ] [http://acm.zju.edu.cn/show_problem.php?pid=2144 2144 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2156 2156 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2180 2180 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2189 2189 by javaman ] Vol XIII [http://acm.zju.edu.cn/show_problem.php?pid=2202 2202 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2206 2206 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2213 2213 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2224 2224 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2227 2227 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2242 2242 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2244 2244 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2254 2254 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2255 2255 by Vegetable Bird ] [http://acm.zju.edu.cn/show_problem.php?pid=2264 2264 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2271 2271 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2278 2278 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2280 2280 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2281 2281 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2283 2283 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2284 2284 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2297 2297 by javaman ] Vol XIV [http://acm.zju.edu.cn/show_problem.php?pid=2319 2319 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2337 2337 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2338 2338 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2341 2341 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2349 2349 by Vegetable Bird ] [http://acm.zju.edu.cn/show_problem.php?pid=2353 2353 by Vegetable Bird ] [http://acm.zju.edu.cn/show_problem.php?pid=2354 2354 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2366 2366 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2372 2372 by pandahyx ] [http://acm.zju.edu.cn/show_problem.php?pid=2374 2374 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2397 2397 by javaman ] Vol XV [http://acm.zju.edu.cn/show_problem.php?pid=2401 2401 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2402 2402 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2414 2414 by Vegetable Bird ] [http://acm.zju.edu.cn/show_problem.php?pid=2422 2422 by jueyey ] [http://acm.zju.edu.cn/show_problem.php?pid=2424 2424 by javaman ] [http://acm.zju.edu.cn/show_problem.php?pid=2432 2432 by javaman] [http://acm.zju.edu.cn/show_problem.php?pid=2498 2498 by Vegetable Bird] Vol XVI [http://acm.zju.edu.cn/show_problem.php?pid=2501 2501 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2521 2521 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2522 2522 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2527 2527 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2536 2536 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2547 2547 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2561 2561 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2563 2563 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2565 2565 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2568 2568 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2581 2581 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2591 2591 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2598 2598 by caopeng] Vol XVII [http://acm.zju.edu.cn/show_problem.php?pid=2604 2604 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2621 2621 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2624 2624 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2625 2625 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2626 2626 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2641 2641 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2642 2642 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2667 2667 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2673 2673 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2683 2683 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2685 2685 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2692 2692 by caopeng] Vol XVIII [http://acm.zju.edu.cn/show_problem.php?pid=2702 2702 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2710 2710 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2711 2711 by Vegetable Bird] [http://acm.zju.edu.cn/show_problem.php?pid=2734 2734 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2739 2739 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2744 2744 by caopeng] [http://acm.zju.edu.cn/show_problem.php?pid=2745 2745 by caopeng]