动态规划算法一般用来求解最优化问题，当问题有很多可行解，而题目要求寻找这些解当中的“最大值”/“最小值”时，通常可以采用DP。
-
01背包问题
有n个重量和价值分别为wi，vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
输入
n=4
(w,v)={(2,3),(1,2),(3,4),(2,2)}
W=5
----------
输出
7
递归函数搜索
（1）有两种可能:选或者不选；（2）使用递归，在遍历完n个数的时候，判断价值最大。
int rec(int i,int j){//最初的j代表W
int res;
if(i==n){
//已经没有剩余物品了
res=0;
}
else if(j<w[i]){
//无法挑选这个物品
res=rec(i+1,j);
}
else{
//挑选和不挑选的这两种情况都尝试一下
res=max(rec(i+1,j), rec(i+1,j-w[i]) + v[i]);
}
return res;
}
动态规划
记dp[i][j]为根据rec的定义，直接利用递推式和二重循环计算出各项的值
for(int i=n-1;i>=0;i--){ //i逆向进行
for(int j=0;j<=W;j++){
if(j<w[i])
dp[i][j]=dp[i+1][j];
else
dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
}
}
关于状态转移方程的循环i方向问题，跟其递推关系定义有关；如果是如下定义，则i的循环能正向进行。
dp[i+1][j]=dp[i][j]; (j<w[i])
dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]); (其他)
个人理解总结:
最重要就是动态转移方程：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
/*
该问题可以描述为 “将前 i 件物品放入容量为 j 的背包中”；
问题可以转换为“只考虑第 i 件物品的策略（放或不放）”，
如果不放第 i 件物品，那么问题就转化为 “前 i-1 件物品放入容量为 j 的背包中”;
如果放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − w[i] 的背包中”;此时获得的最大价值就是 dp[i-1][j-w[i]]+v[i]
*/
具体实现：
//Time: O(nW) Memory: O(nW)
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int w[] = new int[n+1];
int v[] = new int[n+1];
for (int i = 1; i <= n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
}
int W = in.nextInt();
int dp[][] = new int[n+1][W+1];
for (int i = 1; i <= n; i++) {
for (int j = W; j > 0; j--) {
if(j < w[i])
dp[i][j] = dp[i-1][j];
else
dp[i][j] =
Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
System.out.println(dp[n][W]);
}
优化空间复杂度：
如果只用一个数组 dp[W] ，能不能保证第 i
次循环结束后 dp[W] 中表示的就是我们定义的状态 dp[i,W] 呢？ dp[i,W] 是由 dp[i-1 ,W] 和
dp[i − 1,W-w[i] ] 两个子问题递推而来，能否保证在推 dp[i,W] 时（也即在第 i 次主循环中
推 dp[W] 时）能够取用 dp[i − 1,W] 和 dp[i − 1,W− w[i] ] 的值呢？
事实上，这要求在每次主循环中我们以 重量 W 递减顺序计算 dp[W] ，这样才
能保证计算 dp[W] 时 dp[W− w[i] ] 保存的是状态 dp[i − 1, W − w[i]] 的值。
//Time: O(nW) Memory: O(W)
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int W = in.nextInt();
int w[] = new int[n+1];
int v[] = new int[n+1];
for (int i = 1; i <= n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
}
int dp[] = new int[W+1];
for (int i = 1; i <= n; i++) {
for (int j = W; j > 0; j--) {//关键所在
if(j < w[i])
dp[j] = dp[j];
else
dp[j] =
Math.max(dp[j],dp[j-w[i]]+v[i]);
}
}
System.out.println(dp[W]);
}
初始化细节：
我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目
要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别
这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了 F[0] 为 0 ，其它
F[1..V ] 均设为 −∞ ，这样就可以保证最终得到的 F[V ] 是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 F[0..V ]
全部设为 0 。
-
最长公共子序列问题（LCS）
先科普下最长公共子序列 & 最长公共子串的区别： 找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的；而最长公共子序列则并不要求连续。
题目：给定两个字符串s1s2...sn和t1t2...tn;求出这两个字符串的最长公共子序列的长度。
输入
n=4
m=4
s="abcd"
t="becd"
----------
输出
3（"bcd"）
定义dp[i][j]为s1s2...sn和t1t2...tn的公共子序列的长度,再结合图和代码就很容易理解。
/*
问题可以转换为 “s中的前i个字符与t中的前j个字符的公共子序列长度dp[i][j]”；
如果当前s[i]==t[j],那么问题就转变为 “s中的前i-1个字符与t中的前j-1个字符的公共子序列长度 dp[i-1][j-1]+1 ”；
如果不相等，那么问题的转变就有两种可能性；
（1）s中的前i个字符与t中的前j-1个字符的公共子序列长度dp[i][j-1]；
（2）s中的前i-1个字符与t中的前j个字符的公共子序列长度dp[i-1][j]；
*/
int dp[][] = new int[n+1][m+1];
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(s[i-1]==t[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
}
}
System.out.println(dp[n][m]);
- 最长公共子串问题
最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
//动态规划
public class Main
{
static int f(String s1, String s2)
{
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int[][] a = new int[c1.length+1][c2.length+1];
int max = 0;
for(int i=1; i<a.length; i++){
for(int j=1; j<a[i].length; j++){
if(c1[i-1]==c2[j-1]) {
a[i][j] = a[i-1][j-1]+1;
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
public static void main(String[] args){
int n = f("abcdkkk", "baabcdadabc");
System.out.println(n);
}
}
