动态规划(3)

300. 最长递增子序列

1.解法错误

 public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length+1];Arrays.fill(dp,1);for (int i = 0; i < nums.length; i++){for (int  j = 0;j<i;j++){if (nums[i]>nums[j]){dp[i] = Math.max(dp[i], dp[j] + 1);}}}return dp[nums.length-1];
}

原因：(只考虑局部最优解 未考虑道全局)

2.选取全局最优

public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length+1];Arrays.fill(dp,1);for (int i = 0; i < nums.length; i++){for (int  j = 0;j<i;j++){if (nums[i]>nums[j]){dp[i] = Math.max(dp[i], dp[j] + 1);}}}int res = 0;for (int i = 0; i < nums.length; i++){res = Math.max(res, dp[i]);}return res;}

3.二分算法(下午再编辑)