1143.最长公共子序列

思路就是二维dp,dp[m][n]表示，第一个序列长度为m，第二个为n时的最长公共子序列
状态转移方程：
当当前两个序列的值相等时，我们更新当前最大序列长度为dp[i-1][j-1]+1
他情况为Math.max(dp[i-1][j],dp[i][j-1])

我们可以用一维数组解决这个问题，因为当前状态跟本次的上一个状态和上一个本次状态有关，也和上一次的上一个状态有关（这个需要用一个变量每次存储）

classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){intn=text1.length(),m=text2.length();int[]dp=newint[m+1];for(inti=1;i<=n;i++){intprev=0;for(intj=1;j<=m;j++){inttemp=dp[j];if(text1.charAt(i-1)==text2.charAt(j-1)){dp[j]=prev+1;}else{dp[j]=Math.max(dp[j-1],dp[j]);}prev=temp;}}returndp[m];}}