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

上一篇讲了 DP 的基本思想这一篇上难度——最长递增子序列LIS和编辑距离是面试中出现频率很高的 DP 题。一、最长递增子序列publicintlengthOfLIS(int[]nums){intnnums.length;int[]dpnewint[n];Arrays.fill(dp,1);intmaxLen1;for(inti1;in;i){for(intj0;ji;j){if(nums[j]nums[i]){dp[i]Math.max(dp[i],dp[j]1);}}maxLenMath.max(maxLen,dp[i]);}returnmaxLen;}二、编辑距离publicintminDistance(Stringword1,Stringword2){intmword1.length(),nword2.length();int[][]dpnewint[m1][n1];for(inti0;im;i)dp[i][0]i;for(intj0;jn;j)dp[0][j]j;for(inti1;im;i){for(intj1;jn;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];} 觉得有用的话点赞 关注【张老师技术栈】吧