动态规划DP是算法中最重要也最难掌握的思想。这篇从两个经典问题入手讲清楚 DP 的核心套路。一、DP 的核心思想DP 最优子结构 重叠子问题 1. 把大问题拆成小问题状态定义 2. 找到小问题之间的关系状态转移方程 3. 从小问题开始算到大问题递推DP 与分治的区别分治的子问题互不重叠如归并排序DP 的子问题会重复出现如斐波那契。二、斐波那契数列入门// 递归O(2^n)大量重复计算intfib(intn){if(n1)returnn;returnfib(n-1)fib(n-2);}// DPO(n)intfib(intn){if(n1)returnn;int[]dpnewint[n1];dp[0]0;dp[1]1;for(inti2;in;i)dp[i]dp[i-1]dp[i-2];returndp[n];}三、0-1 背包publicintknapsack(int[]weights,int[]values,intcapacity){intnweights.length;int[][]dpnewint[n1][capacity1];for(inti1;in;i){for(intw1;wcapacity;w){if(weights[i-1]w){dp[i][w]dp[i-1][w];// 装不下}else{dp[i][w]Math.max(dp[i-1][w],// 不装dp[i-1][w-weights[i-1]]values[i-1]// 装);}}}returndp[n][capacity];}四、最长公共子序列publicintlongestCommonSubsequence(Stringtext1,Stringtext2){intmtext1.length(),ntext2.length();int[][]dpnewint[m1][n1];for(inti1;im;i){for(intj1;jn;j){if(text1.charAt(i-1)text2.charAt(j-1)){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]Math.max(dp[i-1][j],dp[i][j-1]);}}}returndp[m][n];} 觉得有用的话点赞 关注【张老师技术栈】吧