解决DP(动态规划)问题是需要思维训练的，下面列举了四个经典的DP问题和解析，希望对大家有帮助。
【题目比较长，在此略去了，可以从网上搜到具体描述。】
（一）最长单调递增子序列问题（递减同理）
(1)用一个数组b[n]记录以a[i]结尾的最长单调递增子序列的长度
(2)b[i] = max{a[k] | a[k] < b[k]，0 ≤ k ＜ i} + 1, b[0] = 1
(3)序列a的最长单调子序列的长度为max{b[i], 0 ≤ i ＜ n}
（二）最大子序列和问题
(1)用一个数组b[n]记录以a[i]结尾的最大子序列和
(2)b[i] = max{a[j] + b[i-1], a[j]}
(3)序列a的最大子序列和为max{b[i], 0 ≤ i ＜ n}
（三）最大子矩阵和问题（上题的二维扩展）
(1)限定列的范围（i~j）
(2)对列范围内的每一行求和，从而化为一维序列
(3)化归为问题（二）
（四）背包问题
(1)用一个二维数组m，m[i][j]代表在承重j，装入物品为从i到n时可以达到的最大价值
(2)m[i][j] = max(m[i+1][j], m[i+1][j-wi]+vi)
(3)m[1][j]即为最大价值
（五）滑雪问题
(1)用一个结构体数组LocHeight记录每个点的坐标和高度
用一个二维数组len记录以每个点作为路径起点的最长路径长度
(2)将结构体数组按照高度从低到高排序
注：排序的好处是，处理某个点的时候已经处理完比该点低的所有点的信息，只需一次扫描
(3)对于某点A，四周比A点低的所有点中，选len值最大的点B，将A对应的len值设为B.len+1
(4)扫描len数组，找出最大值