您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【Leetcode】动态规划分类总结

一 接龙型动态规划

题目一般是告诉你一个接龙规则,让你找最长的“龙”。

解题要点有两个:

(1)要把「接龙规则」提炼并表示出来

(2)需要用“倒推法”(通常是写一个getPath()函数),获取最长‘龙’的具体方案。这就往往需要一个与dp[i]唯独相同的数组prev[i]记录,是哪个j(j

代表题目:

  • Leetcode#300. Longest Increasing Subsequence
  • Lintcode#398. Longest Continuous Increasing Subsequence II
  • Leetcode#368. Largest Divisible Subset

1. Leetcode#300. Longest Increasing Subsequence

  • 题目:输入一个int[],找出从左到右的连续上升的子序列
  • 接龙规则:从左到右挑选数,数要一个比一个大
  • 状态表示:dp[i] 表示以第i个数结尾的Incresing subsequence最长是多长 --> return max(dp[0,...n-1])
  • 转移方程:dp[i] = max(dp[j] + 1),其中j < i, 且nums[j] < nums[i]
  • 初始状态:dp[0,...n-1] = 1, prev[0,...n-1] = -1;

2. Lintcode#398. Longest Continuous Increasing Subsequence II

  • 题目:输入一个int矩阵,找出矩阵中最长的LCIS,开一从任意位置开始
  • 接龙规则:(1) 数要一个比一个大 (2)坐标要连续-->只能往上下左右四个方向走(要保证不越界)
  • 状态表示:dp[x][y] 表示以第(x,y)个数结尾的Incresing subsequence最长是多长 --> return max(dp)
  • 转移方程:dp[x][y] = max(dp[x][y], dp[nx][ny]+1), 其中nx = x+dy, ny = y + dy, 且A[nx][ny] > A[x][y]
  • 初始状态:All dp[x][y] = 1;

3. Leetcode#368. Largest Divisible Subset

  • 题目:输入一个int[] nums,找出一个元素最多的subset,满足其中任意两个元素都有: answer[i] % answer[j] == 0, or answer[j] % answer[i] == 0
  • 接龙规则:(需将该集合sort)后一个数必须可以整除前一个数
  • 状态表示:dp[i]表示以nums[i]结尾的最大subset的大小
  • 转移方程:dp[i] = max(dp[i], dp[j] + 1) 其中j < i && nums[j]是nums[i]的因子
  • 初始状态:dp[0,...n-1] = 1

...

二 背包型动态规划

三 坐标型动态规划

四 前缀型动态规划

五 区间型动态规划


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进