//什么是动态规划// 1.动态规划是一种数学方法，一般应用于多决策过程，用来求最优化的问题。 2.动态规划通过定义问题的状态以及状态之间的关系，来拆分问题，使得问题能够以递推的方式被解决。 3.如何观察问题，定义问题的状态，从而对问题进行拆分，这是动态规划的关键之处。 4.另一方面，对于一个问题，以什么作为状态，并不固定，需要有丰富的经验、很强的观察能力和分析能力。这也是大家觉得动态规划比较难掌握的地方。 //构造最优解// 由状态转移方程，就可以计算出所有的状态。

注意：状态并不一定是最终的最优解，有时候还要通过状态再进行计算，来构造出问题的最优解。

//动态规划的实现// 1.图表实现 定义状态和状态转移方程以后，就可以根据状态画出图（或表格），然后按照拓扑排序依次更新每个状态的值。 例如：对于 1 7 2 8 3 4，找 LIS a[] 1 7 2 8 3 4 Fi/dp[] 1 2 2 3 3 4 b[] 1 1 3 5 (b[]表示记录是从前面哪个元素来的) 上图从左到右填充，例如： 首先填写F1，值为1 然后填写F2，F1+1 = 2 F3，F1+1 = 2 F4，max(F1,F2,F3)+1 = 3 F5，max(F1,F3)+1 = 3 F6，max(F1,F3,F5)+1 = 4 2.递归编程 显然，可以用递归函数的方式来编写以上状态转移方程。

int f(int k) {
  if(k==1) return 1;
  //序列的数组从下标1开始
  int r=0;
  for(int i=1; i<k; i++) {
    if (a[i] < a[k]) r=max(r, f(i)+1);
  }
  return r;
}

要注意的是，递归会产生大量的重复计算，例如： f(k) -> f(k-1)、f(k-2)...f(1) f(k-1) -> f(k-2)...f(1) ...... 这是一个树，总共结点规模约为k^k 这样的运算量显然有问题，于是要把这些重复的计算存储起来，下次用到的时候重用。

//记忆递归// 假设用一个状态数组dp[N]存储前面运算过的状态，则代码变成：

int dp[N];
int f(int k) {
  if(k==1) return 1;
  int r=0;
  for(int i=1; i<k; i++) {
    int tmp;
    if(dp[i]) tmp = dp[i];
    else tmp = dp[i] = f(i);

    if (a[i] < a[k]) r=max(r, tmp+1);

  }
  return r;
}
/*
f(1),f(2),...,f(n)
    f(n) (f(1)...f(n-1))
    dp[1]=1;
dp[2]=dp[1]+1;a[1]<a[2]
*/

//递推// 用数组存储每次运算好的状态，然后依次往后递推。

int dp[N];
int f(int k) {
  dp[1] = 1;
  for(int i=2; i<=k; i++) {
    int m = 0;
    for(int j=1; j<i; j++) {
      if(a[i] > a[j]) m=max(m, dp[j]+1);
    }
    dp[i]=m;
  }
  return dp[k];
}

//学习中的questions// 四步走要记住！！！ 在完成一切以后记得看一下变量类型

之前就有不少例子，因为数据太大，导致爆掉 在ICPC中真的很肉疼... 注意范围过大要用long long