介绍
动态规划(简称DP )是算法设计思想中最难最无私的钻石部分。 动态规划适用于重叠子问题和具有最优子结构性质的问题，在数学、计算机科学、经济学中很常用，是将原问题分解为比较简单的子问题来求解复杂问题的方法。 使用动态规划方法求解问题，时间效率较高。 重要的是大幅减少不必要的计算和重复计算的部分
其思想是将大问题进行分割，细分为小问题，再由该小问题的解导出原问题的解。 要进行动态规划，必须满足以下两个重要性质
最优子结构性：是分割后的子问题的解是最优解。
子问题的重叠性质：在求解过程中，但每次出现的子问题并不一定是新的问题，有些子问题被多次重复计算。 动态规划算法利用了这种子问题的重叠性质，每个子问题只计算一次，将其计算结果保存在一个表中，当需要再次计算计算完毕的子问题时，只需在表中简单地看一下结果，就可以获得较高的计算效率
提高警惕
首先，引用动态规划的经典问题，最长不降低子序列
其定义是在：中设定由n个不同整数构成的数列b[n]，如果有下标$i_1的话
例如
13、7、9、16、38、24、37、18、44、19、21、22、63和15
有一个长度为1316384463的不下降的子串。
但是，观察结果显示，实际上有79161819212263长度为8的不下降子串，所以会有更长的不下降子串吗？ 请找到最长的不下降子序列
输入格式
第一行为n，n个(n=100000 )，表示第二行为n个数值)数字之间用空格分开，在最后的数字末尾不能留下空格)。
输出格式
表示最长子序列长度的整数。
输入示例
4
1 3 1 2
输出示例
2
想法
当要求某一段的最优时，考虑如何求更短段的最优，看最短段的最优能否扩大推广到最大段的最优；
假设这样的表：
第3行表示该序列元素的可连接的最长的不下降子序列的长度，由于自身的长度为1，所以初始值全部为1
第4行表示形成与哪个数组元素链接最长不下降的子数组
从倒数第二项63开始计数，后面只有一项，所以只比较一次。 因为是6315，所以从63出发，不做任何链接。 长度果然是1。
看倒数第三项22，后面有两项，所以必须在这两项中找到大于22且长度最长的数值作为链接。 因为只有2263，所以将22的长度加上2，即与自己的长度链接的数值的长度，将链接位置修正为13，即63的下标。
如果你看倒数第四项21，你必须在这三项中找到一个大于21、长度最长的数值作为链接，注意：是长度。 因为很容易看出数值22满足了这个条件，所以将21的长度修正为3，将链接位置修正为12，即22的排列下标。
依次，最后结果如下表：所示
最终状态的迁移方程式为：$f(I )=max ) f ) j )1) b_j
代码
process.stdin.setencoding(UTF8 )；
var arr=[]；
var bool=0；
var n=0；
var longest=1；
var a=[]；
var dp=[]；
process.stdin.on('readable '，function ) )。
var chunk=process.stdin.read (；
if(chunk！==null ) {
ARR.push(chunk.Trim ) )
}
if(bool=2) {
n=arr[0]；
process.stdin.Emit('end ' ) )。
}
布尔
)；
process.stdin.on('end '，function ) {
a=ARR.Slice(1).join (' ).split (' ).map ) function ) index，elem ) {
return parseint (索引；
() )
for(letI=0； I
dp[i]=1；
}
for(letI=1； I
for(letj=0； Jj
if(a ) I ) a ) j ) )
dp[i]=math.max(DP[j]1，DP[I] ) )。
}
longest=math.max(DP[I]，longest ) )。
}
}
console.log ('最长长度为：' longest )；
process.stdout.write('end )；
)；