数据结构——动态规划进阶：最长递增子序列、编辑距离

上一篇讲了 DP 的基本思想，这一篇上难度——最长递增子序列（LIS）和编辑距离是面试中出现频率很高的 DP 题。

一、最长递增子序列

publicintlengthOfLIS(int[]nums){intn=nums.length;int[]dp=newint[n];Arrays.fill(dp,1);intmaxLen=1;for(inti=1;i<n;i++){for(intj=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=Math.max(dp[i],dp[j]+1);}}maxLen=Math.max(maxLen,dp[i]);}returnmaxLen;}

二、编辑距离

publicintminDistance(Stringword1,Stringword2){intm=word1.length(),n=word2.length();int[][]dp=newint[m+1][n+1];for(inti=0;i<=m;i++)dp[i][0]=i;for(intj=0;j<=n;j++)dp[0][j]=j;for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;}}}returndp[m][n];}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！