Dynamic Programming(1)

连续的笔试面试，碰到了好几次动态规划的题，都没有写全，终于下定决心来搞定它，权当笔记，行家莫笑。
有DP解的算法问题要求两个条件：1) 最优子结构 2)重叠子问题，这是DP的核心。一下分别列出几个经典的DP问题。

---

1. 0-1背包问题
在一定容量的背包中放物品，求得到价值最大的情况，代码如下所示：

int set_package(int* W, int* V, int n, int C);
int main()
{
   int W[] = {35, 30, 60, 50, 40, 10, 25};      // 物体重量
   int V[] = {10, 40, 30, 50, 35, 40, 30};      // 物体价值
   int n = 7;                                   // 几个物体
   int capacity = 150;                          //  背包容量
   int value = set_package(W, V, n, capacity);  // 动态规划
   cout << "Total max value is: " << value << endl;
}  

// W: 重量,  V: 价值,  n: 物体种类  C: 背包容量 
int set_package(int* W, int* V, int n, int C) 
{     
    int i, j;     
    int** tabv = new int*[C+1];  
    // 存放动态规划临时结果     
    for (i = 0; i <= C; i++)
         tabv[i] = new int[n+1];
    bool* index = new bool[n];    // 某一物体是否被放入背包      
    for (i = 0; i <=C; i++)       // 初始化最左一列和最下一行  
         tabv[i][0] = 0;     
    for (j = 0; j <= n; j++)  
         tabv[0][j] = 0;          
    
    // 在每个容量i下，去装前j个物体所能达到的最大价值放入tabv[i][j]中     
    for (i = 1; i <= C; i++){         
        for (j = 1; j <= n; j++) {      
            if (i >= W[j-1]) // 若背包能装下j物体，W[j-1]代表j物体重量
         tabv[i][j] = cal_max(V[j-1]+tabv[i-W[j-1]][j-1], tabv[i][j-1]);
     else
  tabv[i][j] = tabv[i][j-1]; 
               // 若装不下，则最大价值就是前j-1个物体最大价值
 }
    }

   // 从tabv数组反求物体列表
   i = C;
   for (j = n; j > 0; --j) {
   // 如果i容量下，装前j个物体价值大于前j-1个物体最大价值，则第j个物体肯定被装到包里
        if (tabv[i][j] > tabv[i][j-1]) {    
              index[j-1] = true;
              i -= W[j-1];  // substract weight of the jth object
         }
         else
              index[j-1] = false; //
   }

   // 打印结果，省略...
   return tabv[C][n];   //返回结果
}

    这里中间过程的表格其实可以缩减到一维，因为tabv[i][j]只用到j-1列的值，所以可以改进空间复杂度为O(C)而非O(nC)，这个比较简单，就不贴上来了。值得注意的是这样要找到哪几个物体被选中就变得复杂一些，需要中间记下一些变量。