DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。

斐波那契数列

  1. #include<stdio.h>
  2. int main(){
  3.     int i;
  4.     long long d[80];
  5.     d[0]=1;
  6.     d[1]=1;
  7.     for(i=2;i<80;i++){
  8.         d[i]=d[i-1]+d[i-2];
  9.     }
  10.     printf("%lld\n",d[79]);
  11.     return 0;
  12. }

上面这个循环d[i]只依赖于前两个数据d[i - 1]和d[i - 2]；为了节约空间用滚动数组的做法。

  1. #include<stdio.h>
  2. int main(){
  3.     int i;
  4.     long long d[3];
  5.     d[1]=1;
  6.     d[2]=1;
  7.     for(i=2;i<80;i++){
  8.         d[0]=d[1];
  9.         d[1]=d[2];
  10.         d[2]=d[0]+d[1]; 
  11.     }
  12.     printf("%lld\n",d[2]);
  13.     return 0;
  14. }

另一种形式：

  2. #include<stdio.h>
  3. int main(){
  4.     int i;
  5.     long long d[3];
  6.     d[0] = 1;
  7.     d[1] = 1;
  8.     for(i=2;i<80;i++){
  9.         d[i%3]=d[(i-1)%3]+d[(i-2)%3];
  10.     }
  11.     printf("%lld\n",d[79%3]);
  12.     return 0;
  13. }

二维数组

  1. int i, j, d[100][100];
  2. for(i = 1; i < 100; i++)
  3.     for(j = 0; j < 100; j++)
  4.         d[i][j] = d[i - 1][j] + d[i][j - 1];

上面的d[i][j]只依赖于d[i - 1][j], d[i][j - 1];运用滚动数组

  1. int i, j, d[2][100];
  2. for(i = 1; i < 100; i++)
  3.     for(j = 0; j < 100; j++)
  4.         // 优化成了一个2*2的数组
  5.         d[i % 2][j] = d[(i - 1) % 2][j] + d[i % 2][j - 1];

0-1背包

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
于其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
此时dp[j]有两个选择：

  • 取自己dp[j]
  • 取dp[j - weight[i]] + value[i]，容量为j的背包放入物品后增加的最大物品价值

倒叙遍历是为了保证物品i只被放入一次！