网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

【Leetcode】动态规划分类总结

2021/6/27 4:52:03 人评论

一 接龙型动态规划 题目一般是告诉你一个接龙规则,让你找最长的“龙”。 解题要点有两个: (1)要把「接龙规则」提炼并表示出来 (2)需要用“倒推法”(通常是写一个getPath()函数)…

一 接龙型动态规划

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

解题要点有两个:

(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

...

二 背包型动态规划

三 坐标型动态规划

四 前缀型动态规划

五 区间型动态规划

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?