最近面试经常被问到动态规划，所以自己做了一个总结，希望能进行深入的理解然后尝试能不能找到通用的解决手段。我觉得动态规划思想好理解，难的是怎么找出全部并且合理的子问题和出口。
我一般把问题分为两类，一类是有两个变化值，对应的我们要设一个二维数组记录（比如背包问题，每一步不仅物品发生变化，背包容量也改变）；一类是一个变化值，对应的我们只需设置一个一维数组（比如只有一个变量改变的最值问题）。
然后确定该问题的子问题，找出状态转移方程。这里有一个小技巧，一般都是从数组最后一个元素开始逐步向前递归（思考方式也就是从最后一个开始思考），然后找递归出口即可。
从0-1背包问题说起：
一个背包总容量为W, 现在有N个物品, 第i个物品容量为w[i], 价值为v[i], 物品只能取或不取，现在往背包里面装东西, 怎样装才能使背包内物品总价值最大？
首先我们看到每一次选取，物品个数和背包容量都会发生变化，所以考虑设一个二维数组B[i][j]，表示i个物品和容量为j的背包的问题，然后找它的子问题：
1 第i个体积太大，放不进去 W不变，i变为i-1。问题转化为i-1个物品和容量为W背包的问题
2 第i个体积不大，可以放进去
（1）放进去 W变为W-w[i]，i变为i-1 问题转化为i-1个物品和容量为W-w[i]背包的问题
（2）不放进去 W不变 i变为i-1 问题转化为i-1个物品和容量为W背包的问题
除此以外应该没有其他可能了，所以我们找出了所有的子问题
写出c代码
#include<stdio.h>
#include <stdlib.h> int B[6][20];
int w[6] = { 0, 2, 3, 4, 5, 9 };
int v[6] = { 0, 3, 4, 5, 8, 10 };int bag(int n, int W){
if (n == 0 || W == 0){
return 0;
}
else{
if (w[n] > W){
return bag(n - 1, W);
}
else{
return (bag(n - 1, W - w[n]) + v[n]) > bag(n - 1, W) ? (bag(n - 1, W - w[n]) + v[n]) : bag(n - 1, W);
}
}
}int main()
{
printf("hello world!\n");
printf("%d", bag(6, 20));
system("pause");
return 0;
}
接下来再来一个一维数组的：
从一个序列中选出互不相邻的几个数，是它们的累加和最大。比如[3,2,1,9,4,2]最大的就是3+9+2=14
求解：
可以看到，每选一个数，这个序列就会改变一次（因为不能再选与被选数相邻的），不存在其他变量，所以我们设一个一维数组num[i]，i表示长度为i的数组（也可以说最后元素下标为i的数组）能选出的最大累加和，设第i个的值为v[i]。
然后找它的子问题：
1 选择第i个 因为不能选择第i-1个数，所以问题转化为长度为i-2的数组+v[i]的子问题
2 不选择第i个，问题转化为长度为i-1的数组的子问题
我们只要找出两者最大即可
代码：
#include<stdio.h>
#include <stdlib.h> int v[6] = { 3, 2, 1, 9, 4, 2 };int add(int *value,int N){
if (N == 0){
return 0;
}
else if (N == 1){
return value[0];
}
else{
return add(value, N - 1) > (add(value, N - 2) + value[N - 1]) ? add(value, N - 1):(add(value, N - 2) + value[N - 1]);
}
}int main()
{
printf("%d", add(v,6));
system("pause");
return 0;
}
这两个还是比较简单的，但是我希望能从简单问题找出通用套路。如果大家有其他的更好的思路可以给我留言。
