序列型动态规划
文章图片

265. 粉刷房子 II ---- 序列型动态规划

文章图片

文章图片

动态规划组成部分一：确定状态
动态规划组成部分二：转移方程
文章图片


文章图片

文章图片

优化后代码：

public int minCost(int[][] A) { if(A.length == 0){ return 0; } int n = A.length; int k = A[0].length; int[][] f = new int[n + 1][k]; int min1,min2; int j1 = 0,j2 = 0; //j1,j2代表最小值和次小值的下标 for(int j = 0; j < k; j++){ f[0][j] = 0; } for(int i = 1; i <= n; i++){ //计算min1,min2(求最小值和次小值) min1 = min2 = Integer.MAX_VALUE; //min1 = f[i - 1][j1] //min2 = f[i - 1][j2] for(int j = 0; j < k; j++){ if(f[i - 1][j] < min1){ //比原来的最小值都小,则把原来的最小值放到次小值里 //然后再把现在的值赋给最小 min2 = min1; j2 = j1; min1 = f[i - 1][j]; j1 = j; }else{ //比最小值大,比次小值小 if(f[i - 1][j] < min2){ min2 = f[i - 1][j]; j2 = j; } } } for(int j = 0; j < k; j++){ if(j != j1){ f[i][j] = f[i - 1][j1] + A[i - 1][j]; }else{ //j == j1(正好是那个最小值) f[i][j] = f[i - 1][j2] + A[i - 1][j]; } } } int res = Integer.MAX_VALUE; for(int j = 0; j < k; j++){ res = Math.min(res,f[n][j]); } return res; }

动态规划常见优化
文章图片


文章图片

文章图片

剑指 Offer II 089. 房屋偷盗 ----- 序列型动态规划??????
动态规划组成部分一：确定状态
文章图片


文章图片

动态规划组成部分二：转移方程
文章图片

简化：

文章图片

动态规划组成部分三：初始条件和边界情况 【java|动态规划刷题攻略(二)】
文章图片

动态规划组成部分四：计算顺序 初始化f[0]
计算f[1]，f[2]，....，f[n]
答案是f[n]
时间复杂度O(N)，空间复杂度O(1)

public int rob(int[] nums) { int n = nums.length; if(n == 0){ return 0; } int[] f = new int[n + 1]; f[0] = 0; f[1] = nums[0]; for(int i = 2; i <= n; i++){ f[i] = Math.max(f[i - 1],f[i - 2] + nums[i - 1]); } return f[n]; }

剑指 Offer II 090. 环形房屋偷盗 ---- 序列型动态规划

文章图片


文章图片

文章图片
小结：

文章图片

买卖股票系列问题 121. 买卖股票的最佳时机

文章图片


文章图片

public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for(int i = 0; i < prices.length; i++){ if(prices[i] < minPrice){ minPrice = prices[i]; }else if(prices[i] - minPrice > maxProfit){ maxProfit = prices[i] - minPrice; } } return maxProfit; }

122. 买卖股票的最佳时机 II

文章图片

只看相邻两点！！！！

文章图片

public int maxProfit(int[] prices) { int res = 0; for(int i = 0; i < prices.length - 1; i++){ if(prices[i + 1] - prices[i] > 0){ res += prices[i + 1] - prices[i]; } } return res; }

123. 买卖股票的最佳时机 III
题目大意和I,II基本相似
只能最多两次买卖
所以需要记录已经买卖了多少次
动态规划组成部分一：确定状态 记录阶段

文章图片


文章图片

文章图片
最后一步

文章图片

文章图片
思考：需要把今天的红利加上

文章图片

子问题

文章图片

动态规划组成部分二：转移方程
文章图片

动态规划组成部分三：初始条件和边界情况
文章图片

动态规划组成部分四：计算顺序
文章图片

public int maxProfit(int[] prices) { int n = prices.length; if(n == 0){ return 0; } int[][] f = new int[n + 1][5 + 1]; //初始条件 //刚开始(前0天),处于阶段1,最大利润为0 f[0][1] = 0; f[0][2] = f[0][3] = f[0][4] = f[0][5] = Integer.MIN_VALUE; for(int i = 1; i <= n; i++){ //1,3,5 for(int j = 1; j <= 5; j += 2){ //max{f[i - 1][j],f[i - 1][j - 1] + Pi - 1 - Pi - 2} f[i][j] = f[i - 1][j]; if(j > 1 && i > 1 && f[i - 1][j - 1] != Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i - 1][j - 1] + prices[i - 1] - prices[i - 2]); } } for(int j = 2; j <= 5; j += 2){ //max{f[i - 1][j] + Pi - 1 - Pi - 2,f[i - 1][j - 1],f[i - 1][j - 2] + Pi-1 - Pi-2} f[i][j] = f[i - 1][j - 1]; if(i > 1 && f[i - 1][j] != Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i - 1][j] + prices[i - 1] - prices[i - 2]); } if(j > 2 && i > 1 && f[i - 1][j - 2] != Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i - 1][j - 2] + prices[i - 1] - prices[i - 2]); } } } return Math.max(Math.max(f[n][1],f[n][3]),f[n][5]); }

188. 买卖股票的最佳时机 IV

文章图片

思考：为啥是 N / 2 ?
如果K > N / 2,并且买了超过一半的次数；此时，一定有几天是连着买卖的(即第一天买，第二天卖，第三天买，第四天卖，第五条买....); 此时可以看作第一天买，第N天买，中间的过程忽略不看，不管咋样买卖的，都可以等价的看作任意一次买卖
动态规划组成部分一：确定状态
文章图片


文章图片

动态规划组成部分二：转移方程
文章图片

动态规划组成部分三：初始条件和边界情况
文章图片

动态规划组成部分四：计算顺序
文章图片

//注意大小写K的区别 public int maxProfit(int K, int[] prices) { int n = prices.length; if(n == 0){ return 0; } int i, j, k; //k > n / 2时,可以看做,任意多次的买卖股票II if(K > n / 2){ int result = 0; for(i = 0; i < n - 1; i++){ result += Math.max(prices[i + 1] - prices[i],0); } return result; } int[][] f = new int[n + 1][2 * K + 1 + 1]; //初始条件 //刚开始(前0天),处于阶段1,最大利润为0 f[0][1] = 0; for(k = 2; k <= 2 * K + 1; k++){ f[0][k] = Integer.MIN_VALUE; } for(i = 1; i <= n; i++){ //1,3,5 for(j = 1; j <= 2 * K + 1; j += 2){ //max{f[i - 1][j],f[i - 1][j - 1] + Pi - 1 - Pi - 2} f[i][j] = f[i - 1][j]; if(j > 1 && i > 1 && f[i - 1][j - 1] != Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i - 1][j - 1] + prices[i - 1] - prices[i - 2]); } } for(j = 2; j <= 2 * K + 1; j += 2){ //max{f[i - 1][j] + Pi - 1 - Pi - 2,f[i - 1][j - 1],f[i - 1][j - 2] + Pi-1 - Pi-2} f[i][j] = f[i - 1][j - 1]; if(i > 1 && f[i - 1][j] != Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i - 1][j] + prices[i - 1] - prices[i - 2]); } if(j > 2 && i > 1 && f[i - 1][j - 2] != Integer.MIN_VALUE){ f[i][j] = Math.max(f[i][j],f[i - 1][j - 2] + prices[i - 1] - prices[i - 2]); } } } int res = Integer.MIN_VALUE; for(i = 1; i <= 2 * K + 1; i += 2){ res = Math.max(res,f[n][i]); } return res; }

序列 + 状态型动态规划小结
文章图片


文章图片

最长序列型动态规划
文章图片

大部分序列型题目通常也是坐标型的，

文章图片

比如这道序列型的题目也可以用坐标型的方法去做(之前的)

文章图片

动态规划组成部分一：确定状态 最后一步

文章图片

子问题

文章图片

动态规划组成部分二：转移方程
文章图片

动态规划组成部分三：初始条件和边界情况
文章图片

动态规划组成部分四：计算顺序
文章图片

public int lengthOfLIS(int[] nums) { int n = nums.length; if(n == 0){ return 0; } int[] f = new int[n]; int res = 0; for(int j = 0; j < n; j++){ //case 1: f[j] = 1; //case 2: for(int i = 0; i < j; i++){ if(nums[i] < nums[j] && f[i] + 1 > f[j]){ f[j] = f[i] + 1; } } res = Math.max(res,f[j]); } return res; }

思考：如何做到nlog(n)[第七讲会讲]

354. 俄罗斯套娃信封问题

文章图片

动态规划组成部分一：确定状态
文章图片

子问题

文章图片

动态规划组成部分二：转移方程
文章图片

动态规划组成部分三：初始条件和边界情况
文章图片

动态规划组成部分四：计算顺序 f[0]，f[1]，...，f[N - 1]
时间复杂度O(N^2),空间复杂度O(N)

public int maxEnvelopes(int[][] envelopes) { if(envelopes.length == 0){ return 0; } Arrays.sort(envelopes,new Comparator(){ public int compare(int[] a,int[] b){ //长度相等,宽度任意排序 if(a[0] == b[0]){ return a[1] - b[1]; }else{ //长度从小到大 return a[0] - b[0]; } } }); int n = envelopes.length; int[] f = new int[n]; int res = 0; for(int i = 0; i < n; i++){ f[i] = 1; for(int j = 0; j < i; j++){ //信封 j 能被放进信封 i if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]){ f[i] = Math.max(f[i],f[j] + 1); } } res = Math.max(res,f[i]); } return res; }

推荐阅读

• 

  借呗2百块钱逾期了怎么办
• 

  杭州有哪些素食餐厅？
• 

  成语有何面目是什么意思 怎么理解有何面目的意思
• 

  黑芝麻能养生保健 食用要注意4点
• 

  2023杭州教资笔试报考幼儿园需要什么学历
• 

  三伏天|哈尔滨人注意！明天开始，长达40天
• 

  怎么打开DPS文件？DPS文件转化为PPT的方法
• 

  爱普生打印机4168废墨盒清零
• 

  2021中秋奇妙游 2021中秋晚会
• 

  香槟色是什么颜色
• 

  狗为什么喜欢刨坑
• 

  海参可以生吃吗
• 

  好用的视频剪辑软件有哪些
• 

  蕉下帽子真有防晒效果吗
• 

  Java日常练习题|Java日常练习题,每天进步一点点(19)
• 

  W索尼最新的 Walkman 型号重燃标志性 Walkman 的精神
• 

  华为ldntl20什么型号 华为ldn
• 

  混的好的人身上都有这三条特征，看看你身上有吗
• 

  基金经理是不是不能买基金
• 

  网页变成黑白色了 网页变成黑白的怎么办

• java|动态规划入门攻略(一)
• 1024程序员节|暴力匹配算法和KMP算法解决字符串匹配问题
• java|java多线程学习万字长文总结
• Java|Java 多线程 万字最详解
• java多线程|万字梳理java多线程的基础知识
• Java|Java多线程学习总结（全面的万字长篇）
• Java 8 判空新写法。。
• 舒服了，踩到一个关于分布式锁的非比寻常的BUG！
• 学习笔记|SpringBoot05（自动配置原理）