https://leetcode.com/problems/longest-increasing-subsequence/description/
// 状态定义：dp[i] 以 nums[i] 为尾的 LIS 长度
// 状态转移方程： dp[i] = Max(dp[j]) + 1 where j < i && nums[j] < nums[i]
// 初始化：all dp items as 1; maxLen as 1
// 循环体：双循环
// 返回target: max value in dp array; not dp[len - 1]
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int maxLen = 1; // case [0], loop will not be excuted.
int[] dp = new int[len];
Arrays.fill(dp, 1);
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
From 九章：
Longest Increasing Subsequence
state:
错误的方法: f[i]表示前i个数字中最长的LIS的长度
正确的方法: f[i]表示前i个数字中以第i个结尾的LIS的长 度
function: f[i] = MAX{f[j]+1}, j < i && a[j] <= a [i])
intialize: f[0..n-1] = 1
answer: max(f[0..n-1])
