<学习笔记>动态规划——初级入门

2017-10-22

最长非降子序列
给定序列a[1],a[2],…a[n],求出最长非降子序列的长度。
沿用求最少硬币的方法，如果我们考虑a[1],a[2],…a[i]的最长非降子序列，其中i

d(1)=1;序列5;子列为5
d(2)=1;序列5,3;子列为5或3
d(3)=2;序列5,3,4;子列为3,4
d(4)=3;序列5,3,4,8;子列为3,4,8
d(5)=3;序列5,3,4,8,6;子列为3,4,8
d(6)=3;序列5,3,4,8,6,7;子列为3,4,8或5,6,7

我们观察这个递推过程，同时思考我们求解这个问题的过程，其实如果求当前前i个元素的结果，就是将前面的子序列中，列尾不大于a[i]
的序列长度加1，如果列尾都大于a[i],那么就要将其置1，产生一个长度为1新的被求子序列。

1 2	d(i)=max{1,d(j)+1}; //j<i;a[j]<=a[i];

根据上面的叙述，我们就可以很容易的写出代码来了。

#include<iostream>
using namespace std;
int main() {
int a[6] = {5,3,4,8,6,7};
int d[6];//存储过程中的序列长度；
int len = 1;//初始化长度为1；
for (int i = 0; i < 6; i++) {
  d[i] = 1;//遍历到一个新的数字，那么假设它比前面的都小，初始化为1；
  for (int j = 0; j < i; j++) {
    if (a[j] <= a[i] && d[j] + 1 > d[i]) {
      d[i] = d[j] + 1;
      //从前面的子列中，找到那个列尾不大于a[i]的序列长度加1；
      //有更长的就要继续更新；
    }
  }
  if (d[i] > len) {
    len = d[i];//找到更长的，就要更新；
  }
}
cout << len << endl;
return 0;
}