算法面试——动态规划：最长回文子串、编辑距离、打家劫舍

DP 题目的核心是定义状态和找到转移方程。一、打家劫舍publicintrob(int[]nums){if(nums.length0)return0;if(nums.length1)returnnums[0];int[]dpnewint[nums.length];dp[0]nums[0];dp[1]Math.max(nums[0],nums[1]);for(inti2;inums.length;i)dp[i]Math.max(dp[i-1],dp[i-2]nums[i]);returndp[nums.length-1];}二、最长回文子串publicStringlongestPalindrome(Strings){intns.length();boolean[][]dpnewboolean[n][n];intstart0,maxLen1;for(inti0;in;i)dp[i][i]true;for(intlen2;lenn;len){for(inti0;ilen-1n;i){intjilen-1;if(s.charAt(i)s.charAt(j)){dp[i][j]len2||dp[i1][j-1];}if(dp[i][j]lenmaxLen){starti;maxLenlen;}}}returns.substring(start,startmaxLen);} 觉得有用的话点赞 关注【张老师技术栈】吧