动态规划 ( DP ) 和 实例分析

一直都不知道怎么来写这篇博文，真的很难写，主要是怕自己写不好，会造成误解！因为之前自己看的网上的一些文章就是的，不过也有好的~感谢那些大牛！

现在也尝试写吧，写的不好，大家请包涵见谅！

我一般是比较讨厌在bolg上写概念的，因为那真的很无聊，但并不是概念不重要，很重要，但是写出来应该要用比较好理解的描述。一直尝试着怎么去很好的描述DP，也一直在纠结！很多时候是会这一个DP的题目，下一个还是不会，这样真的没什么用，其实对于我自己来说，也是的！悲哀~

好了，不多废话！

我这里说的都是建立在可以DP的情况下！

DP：简单来说就是

1：将一个大的问题小化

2：需要保存小问题的值，来给大的问题使用，或者说直接调用（其实也就是空间换时间）

关键：怎样找到那个小问题，或者说怎么去划分小状态！

同时我觉得，有时候并不一定要写出动态规划的方程，很多时候只是考虑清楚有哪些情况就可以了~

其实到这个地方我就不知道怎么去解释了，因为对于每一个问题来说是不一样的！

或许可以这么想，如果你会这个问题的递归算法，递归是将问题不断减小，然后作为返回参数！那么对于DP来说，不是从大问题开始减小，而是从小问题开始增大，然后解决后面大问题的时候，直接调用前面小问题的解就可以！所以过程基本与递归式相反的！

看个小例子：fibonacci 序列

如果我们使用递归，那么是

 每一条装配线上有n个装配站，编号为j=1,2,...,n，将装配线i(i为1或2)的第j个装配站表示为S(i,j)。装配线1的第j个站S(1,j)和装配线2的第j个站S(2,j)执行相同的功能。然而这些装配站是在不同的时间建造的，并且采用了不同的技术，因此，每个站上完成装配所需要的时间也不相同，即使是在两条装配线上相同位置的装配站也是这样。把每个装配站上所需要的装配时间记为a(i,j)，并且，底盘进入装配线i需要的时间为e(i)，离开装配线i需要的时间是x(i)。正常情况下，底盘从一条装配线的上一个站移到下一个站所花费的时间可以忽略，但是偶尔也会将未完成的底盘从一条装配线的一个站移到另一条装配线的下一站，比如遇到紧急订单的时候。假设将已经通过装配站S(i,j)的底盘从装配线i移走到另一条装配线所花费的时间为t(i,j)，现在的问题是要确定在装配线1内选择哪些站以及在装配线2内选择哪些站，以使汽车通过工厂的总时间最小。

这里我们就直接用DP的思想去考虑问题：我们需要求最短路径，那么对于中间的任意一点来说，只可能有两路径到达自己，从自己这条线的前一个节点，或者是从对面那一条线的对应的前一个节点，那么这题是典型的DP问题，我们从前到后，把每一级的最优解求出来，然后供后面的大问题处理即可!！所以我们需要一个数组来记录每一级的最短的路径值，暂且设为A[2][N]，因为只有两条线，那么A[0][i]代表第一条线的第i个节点的情况；
A[1][i]代表的是第二条线的第i个节点的情况；

其实这一题我们不需要写出状态方程式可以的，我们很清楚最有解只有2个方向过来的，如果从自己的前一个节点来( 例如现在考虑的是第一条线上的点 )，那么就是 A[0][i-1] + cost[i]，如果从对面线的对应前一个节点来，那么就是 A[1][i-1] + cost[i] + t ( t是从对面过来的代价 )
那么去 A[0][i] =  min(A[0][i-1] + cost[i]，A[1][i-1] + cost[i] + t  ) 也就是所谓的状态方程，所以后面的大问题都是由小问题保存的解推出来的！所以DP很方便！
演示参考代码如下：


二：最长递增序列和最长不递增序列( LIS问题 )
写一个时间复杂度尽可能低的程序，求一个一维数组（N个元素）中的最长递增子序列的长度。
分析：例如
举例：
原序列为A[] = { 10，50，80，30，60，70 }
B[] = { ... }
开始遍历A，如果遇到B[top] < A[i]，那么说明是符合递增序列的性质的，那么B[++top] = A[i]，再接着扫描
如果发现B[top] <= A[i]，那么我们知道这个数据会影响序列递增，那么我们需要怎么办？我们尽可能要保证每一个子序列都是尽可能的递增，那么我们需要在B[0]---B[top]找到第一大于A[i]的数(使用二分法，那么节约了时间！)，下标为x，然后B[x] = A[i]；为什么找第一个大于A[i]的数呢？就是为了使得各个子序列尽可能的增序( 此处我也不知道怎么去描述，大家自己也好好想想，很多时候讲不出来，无语~~~)。
那么我们看过程：
B[0] = 10;   //
B[1] = 50;
B[2] = 80;
// 前面三个都是属于B[top] < A[i]，所以加进去即可
再读到30，用30替换50，得到10，30，80；  ( 使用二分法 ) 
再读60，用60替换80，得到10，30，60；再读70，
得到最终栈为10，30，60，70。最长递增子序列为长度4。
代码如下：
0李子4KGNT$45001苹果5KGNT$57002橘子2KGNT$22503草莓1KGNT$11004甜瓜6KGNT$6700

放入李子背包负重12345678value０００45004500450045009000item－－－０００００
放入苹果背包负重12345678value０００45005700570057009000item－－－０111０
放入橘子背包负重12345678value０2250225045005700675079509000item－22０122０
放入草莓背包负重12345678value11002250335045005700680079509050item323０1323
放入甜瓜背包负重12345678value11002250335045005700680079509050item323０1323
我们可以得到最大的值是在最后一个水果放进去，且达到最大的W的时候的值，也就是在背包负重8公斤时，最多可以装入9050元的水果，然后将对应的水果的weight、减去得到8-1=7，那么找w=7时候的最佳解即7950，然后再减去对应水果weight即7-2=5，w=5时候最佳值就是5700，然后5-5=0，ok结束！
代码如下：

#include <stdio.h>#include <stdlib.h>#define MAX_OBJ 10#define MAX_WEI 100typedef struct{int weight;int value;}good, *p_good;int dp_get_max_value( good goods[], int n, int w ){int result[MAX_OBJ+1][MAX_WEI+1];// 存放最终的放入的物品情况！int tmp[MAX_OBJ+1][MAX_WEI+1];// 代表选择几件物品i，在可承受重量j情况下的最大的价值int i, j, x, y;for( i = 0; i < n + 1; ++i ){tmp[i][0] = 0;// 可承受价值为0，那么任意件物品都放不进，所以 = 0；}for( i = 0; i < w + 1; ++i ){tmp[0][i] = 0;// 即使有可以承受的重量，但是我一件物品都不放，那么价值还是 = 0；}i = 1;while( i <= w )// 初始化第一个物品的数据 {if( goods[0].weight > i ){result[1][i] = -1;}else{result[1][i] = 0;}tmp[1][i] = ( int )( i / goods[0].weight ) * goods[0].value;++i;}for( i = 1; i < n; ++i ){for( j = 1; j < w + 1; ++j ){if( goods[i].weight > j ){tmp[i+1][j] = tmp[i][j];result[i+1][j] = result[i][j];}else{tmp[i+1][j] = tmp[i][j] > ( tmp[i][j-goods[i].weight] + goods[i].value ) ? tmp[i][j] : ( tmp[i][j-goods[i].weight] + goods[i].value );if( tmp[i+1][j] == tmp[i][j] )// {result[i+1][j] = result[i][j];}else{result[i+1][j] = i;}}}}/*for( i = 1; i <= n; ++i ){for( j = 1; j <= w; ++j ){printf("%d ", result[i][j]);}printf("\n");}*/printf("选出的物品的id为： ");x = n;y = w;while( y )// 找到所有的id{printf("%d ", result[n][y]);y -= goods[result[n][y]].weight;}printf("\n");return tmp[n][w];}int main(){int n, i, w;p_good goods;printf("输入能承受的最大重量：");scanf("%d", &w);printf("\n输入物品的种类个数：");scanf( "%d", &n );goods = ( p_good )malloc( sizeof( good ) * n );printf("\n输入物品的重量和价值：\n");for( i = 0; i < n; ++i ){scanf("%d%d", &goods[i].weight, &goods[i].value);}printf("最大价值是：%d\n", dp_get_max_value( goods, n, w ));return 0;}

说到现在，感觉有点崩溃，感觉讲解的真烂，哎，大家见谅！
希望能与大家共同学习！谢谢~