代码实现：
/** * 求最长公共子序列问题 * Talk is cheap, show me the code! * 参考公式(也是最难的一步)： * { 0 i = 0, j = 0 * c[i][j] = { c[i-1][j-1]+1 i,j>0, x[i] == y[i] * { max{c[i-1][j],c[i][j-1]} i,j>0, x[i] != y[i] * 参考书目：算法设计与分析（第四版）清华大学出版社 王晓东 编著 * 参考博客：https://www.cnblogs.com/hapjin/p/5572483.html * 比如A = "LetMeDownSlowly!" B="LetYouDownQuickly!" A和B的最长公共子序列就是"LetDownly!" * @param x * @param y * @Param c 用c[i,j]表示：(x1,x2....xi) 和 (y1,y2...yj) 的**最长**公共子序列的长度 * @return 最长公共子序列的长度 */ //maybe private method private static int lcsLength(String x, String y, int[][] c){ int m = x.length(); int n = y.length(); //下面是初始化操作，其实也没必要，因为Java中默认初始化为0，其他语言随机应变 for (int i = 0; i <= m; i++) c[i][0] = 0; for (int i = 0; i <= n; i++) c[0][i] = 0; //用一个序列的每个元素去和另一个序列分别比较 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if(x.charAt(i-1) == y.charAt(j-1)){ //如果遇到相等的，就给序列的上一行上一列的加1 c[i][j] = c[i-1][j-1]+1; }else if(c[i-1][j] >= c[i][j-1]){ //取上一次最大的，保证最长子序列的最长要求 c[i][j] = c[i-1][j]; }else{ c[i][j] = c[i][j-1]; } } } return c[m][n]; } 0-1背包问题也是很经典的一道算法题：0-1背包问题说的是，给定背包容量W，一系列物品{weiht,value}，每个物品只能取一件，计算可以获得的value的最大值。
最优解问题，当然是我们DP，最难的一步还是状态转移方程，我们先把方程给出来，再对其进行讨论.
m[i][j]表示1,2,...,i个物品，背包容量为j时候的最大value，w[i]表示第i个物品的重量，v[i]表示第i个物品的value
我们用一个二维数组来存储这个m，i表示1,2,...,i个物品，j表示背包容量
对于每一个物品来说，要计算当前最大的value，分为两种情况：1、将这个物品放进去，不将这个物品放进去
1、我们先考虑不将其放进去， 很好理解，m[i-1][j]就是不将第i个物品放入背包的最大value，不放就是1,2,...,i-1个物品，背包容量为j
2、再考虑放进去的情况，既然要将其放进去，那就在背包中给其预先留好位置，m[i-1][j-w[i]]表示在背包中先给第i个物品把地方腾出来，然后背包可用空间就是j-w[i],在这些可用空间里1,2,...,i-1个物品放的最大value就是m[i-1][j-w[i]]，将其放进去只需要再给加上v[i]即可，即m[i-1][j-w[i]]+v[i]。
所以状态转移方程就是取放进去和不放进去两种情况的最大值
代码实现
/** * 此函数用于计算背包中能存放的最大values * @param m m[i][j]用于记录1,2,...,i个物品在背包容量为j时候的最大value * @param w w数组存放了每个物品的重量weight,w[i]表示第i+1个物品的weight * @param v v数组存放了每个物品的价值value,v[i]表示第i+1个物品的value * @param C C表示背包最大容量 * @param sum sum表示物品个数 * 状态转移方程: m[i][j] = max{ m[i-1][j-w[i]]+v[i] , m[i-1][j]} * m[i-1][j]很好理解，就是不将第i个物品放入背包的最大value * m[i-1][j-w[i]]+v[i]表示将第i个物品放入背包，m[i-1][j-w[i]]表示在背包中先给第i个物品把地方腾出来 * 然后背包可用空间就是j-w[i],在这些可用空间里1,2,...,i-1个物品放的最大value就是m[i-1][j-w[i]],那 * 最后再加上第i个物品的value，就是将第i个物品放入背包的最大value了 */ public static void knap(int[][] m, int[] w,int[] v, int C, int sum){ for(int j = 0; j < C; j++){ //初始化 stuttering if(j+1 >= w[0]){ //第一行只有一个物品，如果物品比背包容量大就放进去，否则最大value只能为0 m[0][j] = v[0]; }else{ m[0][j] = 0; } } for(int i = 1; i < sum; i++){ for(int j = 0; j < C; j++){ int a = 0, b = 0; //a表示将第i个物品放入背包的value，b表示不放第i个物品 if(j >= w[i]) a = m[i-1][j-w[i]]+v[i]; b = m[i-1][j]; m[i][j] = (a>b?a:b); } } }