最长递增子序列 动态规划

在网上找了好久关于动态规划的入门教程，总是觉得云里雾里看不太懂。

勉强一个可以理解的代码。

正序遍历，从第一位开始

1static int cache[] = new int[100];; 2static int num[] = {9,2,1,7,5,4,2,6}; 3public static void main(String[] args) { 4 Arrays.fill(cache, -1); 5 for (int i = 0; i < A.size(); ++i) { 6 maxLen = Math.max(maxLen,lis(i)); 7 System.out.println(maxLen); 8 } 9} 10public static int lis(int start) {11 if (cache[start] != -1) {12 return cache[start];13 }14 cache[start] = 1;15 for (int next = start+1; next < A.size(); ++next) {16 if (num[start]<num[next]) {17 cache[start] = Math.max(cache[start], lis(next)+1);18 }19 }20 return cache[start];21}22