动态规划法背包问题
动态规划问题为什么用逆序标号法？
动态规划问题为什么用逆序标号法？
对于同一个动态规划问题,逆序法和顺序法的解一样的。 动态规划法是将一个大问题转化为小问题，即重叠子问题，然后递归进行计算，而不管是逆序还是顺序都要讨论到问题的每种可能解，比如01背包问题，不管顺序还是逆序都要讨论每一个物品是否放入，而对同一个问题，明显解是不会变化的，否则不是说明肯定有方法错了。
如何理解递归，回溯，动态规划等算法？
递归比较简单的，就是递推的逆向算法。例如已知a(10)且a(n)=f(a(n 1))，让你求a(1)。回溯是深度优先搜索必须要用到的方法，推荐你看下“八皇后问题”，看完就应该明白了。动态规划是一种以空间换时间的算法，也就是占用内存较大，但是时间效率比较高的分阶段算法。推荐你看看“拦截导弹”问题，“0/1背包问题”。动态规划先多看看题，然后再去理解概念比较好
acm算法？
acm算法：
一.基本算法:
5 (1)枚举. (poj1753,poj2965)
6 (2)贪心(poj1328,poj2109,poj2586)
7 (3)递归和分治法.
8 (4)递推.
9 (5)构造法.(poj3295)
10 (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
11 二.图算法:
12 (1)图的深度优先遍历和广度优先遍历.
13 (2)最短路径算法(dijkstra,bellman-ford,floyd,heap dijkstra)
14 (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
15 (3)最小生成树算法(prim,kruskal)
16 (poj1789,poj2485,poj1258,poj3026)
17 (4)拓扑排序 (poj1094)
18 (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
19 (6)最大流的增广路算法(KM算法). (poj1459,poj3436)
20 三.数据结构.
21 (1)串 (poj1035,poj3080,poj1936)
22 (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
23 (3)简单并查集的应用.
24 (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
25 (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
26 (5)哈夫曼树(poj3253)
27 (6)堆
28 (7)trie树(静态建树、动态建树) (poj2513)
29 四.简单搜索
30 (1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
31 (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
32 (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
33 五.动态规划
34 (1)背包问题. (poj1837,poj1276)
35 (2)型如下表的简单DP(可参考lrj的书 page149):
36 1.E[j]=opt{D w(i,j)} (poj3267,poj1836,poj1260,poj2533)
37 2.E[i,j]=opt{D[i-1,j] xi,D[i,j-1] yj,D[i-1][j-1] zij} (最长公共子序列)
38 (poj3176,poj1080,poj1159)
39 3.C[i,j]=w[i,j] opt{C[i,k-1] C[k,j]}.(最优二分检索树问题)
40 六.数学
41 (1)组合数学:
42 1.加法原理和乘法原理.
43 2.排列组合.
44 3.递推关系.
45 (POJ3252,poj1850,poj1019,poj1942)
46 (2)数论.
47 1.素数与整除问题
48 2.进制位.
49 3.同余模运算.
50 (poj2635, poj3292,poj1845,poj2115)
51 (3)计算方法.
52 1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
53 七.计算几何学.
54 (1)几何公式.
55 (2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
56 (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
57 (poj1408,poj1584)
58 (4)凸包. (poj2187,poj1113)
59