动态规划可以非常显著的降低时间复杂度，提高代码的执行效率。
0-1背包问题
对于一组不同重量、不可分割的物品，选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值。
回溯算法
穷举所有可能的装法，然后找出 满足条件的最大值。0-1背包 回溯算法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//结果
private int maxW = Integer.MIN_VALUE;
//物品重量
private int[] weight = {2,2,4,6,3};
//物品个数
private int n = 5;
//背包承受的最大重量
private int w = 9;
public void f(int i, int cw) {
//cw == w表示装满了，i == n表示物品考察完了
if(cw == w || i == n) {
if(cw > maxW) maxW = cw;
return;
}
f(i+1, cw);//不装第i个物品
if(cw + wight[i] <= w) {
//装第i个物品
f(i+1, cw + weight[i]);
}
}将回溯求解过程转换为递归树
树中的每个节点表示一种状态，用(i,cw)表示。i表示将要决策第几个物品是否装入背包，cw表示当前背包中物品的总重量。
在递归树中，有些子问题的求解是重复的，可以借助递归中的备忘录的解决方式，记录已经计算好的f(i,cw)，当再次计算到重复的f(i,cw)时，直接从备忘录中取出来，避免冗余计算。0-1背包 回溯算法+备忘录1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24//结果
private int maxW = Integer.MIN_VALUE;
//物品重量
private int[] weight = {2,2,4,6,3};
//物品个数
private int n = 5;
//背包承受的最大重量
private int w = 9;
//备忘录，默认值false
private boolean[][] mem = new boolean[5][10];
public void f(int i, int cw) {
//cw == w表示装满了，i == n表示物品考察完了
if(cw == w || i == n) {
if(cw > maxW) maxW = cw;
return;
}
if(mem[i][cw]) return;//重复状态
mem[i][cw] = true;//标记（i,cw）这个状态
f(i+1, cw);//不装第i个物品
if(cw + wight[i] <= w) {
//装第i个物品
f(i+1, cw + weight[i]);
}
}回溯算法解决问题的时间复杂度是O(2n)，是指数级的。
动态规划
把整个求解过程分为多个阶段，每个阶段对应一个决策，记录每一阶段可达的状态集合（去掉重复的），通过当前阶段的状态集合，来推导下一阶段的状态集合，动态的往前推进。对应背包问题，把整个求解过程分为n个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策完之后，背包中的物品的重量会有多种情况，达到多种不同的状态，对应到递归树中，就是很多不同的节点。
把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。动态的往前推进。通过合并每一层重复的状态，这样保证每一层不同状态的个数都不会超过w个(如背包的承载重量w)，成功避免了每层状态个数的指数级增长。
最终，只需要在最后一层找一个值为true的最接近w的值，就是背包中物品总重量的最大值。
0-1背包 动态规划1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32//wight物品重量
//n物品个数
//w背包可承载重量
public int knapsack(int[] weight, int n, int w) {
boolean[][] states = new boolean[n][w+1];//默认值false
//哨兵特殊处理第一行的数据
states[0][0] = true;
if(weight[0] <= w) {
states[0][weight[0]] = true;
}
//动态规划状态转移
for(int i = 1; i < n; ++i) {
//不把第i个物品放入背包
for(int j = 0; j <= w; ++j) {
if(states[i-1][j] == true) {
states[i][j] = states[i-1][j];
}
}
//把第i个物品放入背包
for(int j = 0; j <= w-weight[i]; ++j) {
if(states[i-1][j]==true) {
states[i][j+weight[i]] = true;
}
}
}
//输出结果
for(int i = w; i >= 0; --i) {
if(states[n-1][i] == true)
return i;
}
return 0;
}动态规划代码中，耗时最多的部分就是代码中的两层for循环，时间复杂度是O(n*w)。n表示物品个数，w表示背包可以承载的总重量。
代码中，需要额外申请一个n乘以w+1的二维数组，对空间的消耗比较多。动态规划是一种空间换时间的解决思路。一维数组优化,只记录当前层选择后的最终结果，节省空间，但是无法倒推放入了哪些物品。
0-1背包 动态规划-一维数组1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public static int knapsack(int[] items, int n, int w) {
boolean[] states = new boolean[w+1];//默认值false
//哨兵特殊处理第一行数据
states[0] = true;
if(items[0] <= w) {
states[items[0]] =true;
}
//动态规划
for(int i = 1; i < n; ++i) {
for(int j = w-items[i]; j >= 0; --j) {
if(states[j] == true)
states[j+items[i]] = true;
}
}
//输出结果，最大重量
for(int i = w; i >= 0; --i) {
if(states[i] == true)
return i;
}
return 0;
}j从大到小处理，避免for循环重复计算的问题。
比如 j = 0, item[i] = 5, w=10，如果正向循环，j=0 时会设置 state[5] = true, 而当遍历至 j=5时，由于 state[5]=true，会设置 state[10] = true，但是实际上将 5 这个重量使用了两次，所以导致了重量的重复使用。
0-1背包问题升级版
引入物品价值变量。
对于一组不同重量、不同价值、不可分割的物品，选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值的最大值。
回溯算法
0-1背包升级版 回溯算法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17private int maxV = Integer.MIN_VALUE;
private int[] items = {2,2,4,6,3};
private int[] value = {3,4,8,9,6};
private int n = 5;
private int w = 9;
public void f(int i, int cw, int cv) {
if(cw == w || i == n) {
if(cv > maxV) {
maxV = cv;
}
return;
}
f(i+1,cw,cv);
if(cw+weight[i] <= w) {
f(i+1, cw+weight[i], cv+value[i]);
}
}递归树：
在递归树中，每个节点表示一个状态。用三个变量(i,cw,cv)表示一个状态，其中i表示即将要决策第i个物品是否装入背包，cw表示当前背包中物品的总重量，cv表示当前背包中物品的总价值。
在递归树中，有些节点的i和cw是完全相同的，在背包中物品总重量一样的情况下，某种状态对应的物品总价值更大，可以舍弃同种状态价值小的状态，沿着价值大的决策路线继续往下决策。
对于(i，cw)相同的不同状态，只需要保留cv值最大的状态，继续递归处理，其他状态不予考虑。动态规划
把整个求解过程分为n个阶段，每个阶段决策一个物品是否放入背包中。每个阶段决策之后，背包中的物品的总重量以及总价值会有多种情况。
用一个二维数组states[n][w+1]，来记录每层可以达到的不同状态，数组中存储的是当前状态对应的最大总价值。把每一层中(i,cw)重复的状态节点合并，只记录cv值最大的那个状态，然后基于这些状态来推导下一层的状态。0-1背包升级版 动态规划1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41public static int knapsack(int[] weight, int[] value, int n, int w) {
//n个物品，w+1种重量
int[][] states = new int[n][w+1];
//初始化states
for(int i=0; i<n; ++i) {
for(int j=0; j<w+1; ++j) {
states[i][j] = -1;
}
}
//第一行数据特殊处理
states[0][0] = 0;
if(weight[0] <= w) {
states[0][weight[0]] = value[0];
}
//动态规划，状态转移
for(int i=1; i<n; ++i) {
//不选择第i个物品，上一行该列的状态转移导致本行该列
for(int j=0; j<=w; ++j) {
if(states[i-1][j] >= 0) {
states[i][j] = states[i-1][j];
}
}
//选择第i个物品
for(int j=0; j<=w-weight[i]; ++j) {
if(states[i-1][j] >= 0) {
int v = states[i-1][j] + value[i];
if(v > states[i][j+weight[i]]) {
states[i][j+weight[i]] = v;
}
}
}
}
//找到最大值,必定在最后一行
int maxvalue = -1;
for(int j=0; j<=w; ++j) {
if(states[n-1][j] > maxvalue) {
maxvalue = states[n-1][j];
}
}
return maxvalue;
}时间复杂度为O(n*w),空间复杂度O(n*w)。
结论
大部分动态规划能解决的问题，都可以通过回溯算法来解决。
回溯算法解决起来效率比较低，时间复杂度是指数级的。
动态规划在执行效率方面高很多，但是空间复杂度也提高了。
动态规划是一种空间换时间的算法思想。