算法小抄

动态规划

动态规划三要素

  • 重叠子问题:重复计算

  • 最优子结构:通过子问题的最值得到原问题的最值

  • 状态转移方程:列出正确的「状态转移方程」才能正确地穷举

    #初始化 base case
    dp[0][0][...] = base
    #进行状态转移
    for 状态1 in 状态1的所有取值:
          for 状态2 in 状态2的所有取值:
              for ...
                  dp[状态1][状态2][...] = 求最值(选择1,选择2...)
    

1、确定 base case。
2、确定「状态」,也就是原问题和子问题中会变化的变量。
3、确定「选择」,也就是导致「状态」产生变化的行为,即「选择」。
4、明确 dp 函数/数组的定义。

基本动态规划:一维

  1. 509.斐波那契数(简单)
    状态转移方程:dp[i] = dp[i - 1] + dp[i - 2],可使用状态压缩
  2. 322.零钱兑换(中等)
    状态转移方程:dp[i] = min(dp[i], 1 + dp[i - coin]);
  3. 70. 爬楼梯(简单)
    状态转移方程:dp[i] = dp[i-1] + dp[i-2],可使用状态状态压缩
  4. 198. 打家劫舍(简单)
    状态转移方程:dp[i]=max(nums[i-1]+dp[i-2],dp[i-1]),可使用状态压缩
  5. 413. 等差数列划分(中等)
    状态转移方程:dp[i] = dp[i-1]+1,需要对dp表求和得到最终的结果

基本动态规划:二维

输入是二维时,定义二维的dp数组

  1. 64. 最小路径和(中等)
    状态转移方程:

       if(i==0&&j==0)
           dp[0][0] = grid[0][0];
       else if(i==0)
           dp[i][j] = dp[i][j-1] + grid[i][j];
       else if(j==0)
           dp[i][j] = dp[i-1][j] + grid[i][j];
       else
           dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
    
  2. 542. 01 矩阵
    两个方向的状态转移方程:

     dp[i][j] = Math.min(dp[i][j],dp[i-1][j]+1);
     dp[i][j] = Math.min(dp[i][j],dp[i][j-1]+1);

     dp[i][j] = Math.min(dp[i][j],dp[i+1][j]+1);
     dp[i][j] = Math.min(dp[i][j],dp[i][j+1]+1);
  1. 221. 最大正方形
    状态转移方程:
    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
    maxEdge = Math.max(maxEdge,dp[i][j]);

子序列问题

300. 最长递增子序列
base case: dp[i] = 1
状态转移方程:
for(int j = 0;j < i;j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
354. 俄罗斯套娃信封问题
信封嵌套问题就需要先按特定的规则排序,之后就转换为一个 最长递增子序列问题。先对宽度 w 进行升序排序,如果遇到 w 相同的情况,则按照高度 h 降序排序。之后把所有的 h 作为一个数组,在这个数组上计算 LIS 的长度就是答案。

1143. 最长公共子序列
dp数组定义:dp[i][j]含义是对于s1[0..i-1]和s2[0..j-1],LCS长度是dp[i][j]
base case:dp[0][:]和dp[:][0]初始化为0,表示空串
状态转移方程:
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]);

编辑距离问题

72. 编辑距离
状态转移方程:相等不变,不等增删改
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = min(dp[i-1][j-1]+1,dp[i][j-1]+1,dp[i-1][j]+1);
}

最大子数组问题

53. 最大子序和
dp数组定义 :dp[i]表示以nums[i]结尾的最大子数组和。
状态转移方程:dp[i] = Math.max(dp[i],dp[i-1]+nums[i]);
base case:dp[0] = nums[0];
516. 最长回文子序列
dp定义比较特殊:在子串s[i...j]中,最长回文子序列的长度为dp[i][j]

1312. 让字符串成为回文串的最少插入次数
回文串的dp定义基本相同:dp[i][j]表示i-j子串的相应值
状态转移方程:
if(s.charAt(i)==s.charAt(j))
dp[i][j] = dp[i+1][j-1];
else
dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;

10. 正则表达式匹配

背包问题

0-1背包
dp[i][j] 表示前i个物品,背包容量为j时,能装下的最大价值
base case:dp[0][:] = dp[:][0]=0.表示0个物品或者0容量,最大价值为0
状态转移方程:
if(num[i-1] > j )
dp[i][j]=dp[i-1][j]
else
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i-1]+vals[i-1]);

子集背包
416. 分割等和子集
先求和得sum,转化为背包问题:对N个物品,sum/2的容纳重量,每个物品的重量为nums[i],是否存在一种装法,可以将背包装满?
dp[i][j] 表示 对容量为j的背包,使用i个物品可以将其装满
base case: dp[:][0]=true:没有空间相当于装满了,dp[0][:]=false:没有物品,不可能装满
状态转移方程:
if(nums[i-1] > j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];

完全背包:物品数量无限
518. 零钱兑换 II

分割类型题

  1. 279. 完全平方数

数据结构

二叉树

124. 二叉树中的最大路径和
105. 从前序与中序遍历序列构造二叉树

二叉搜索树
700. 二叉搜索树中的搜索
701. 二叉搜索树中的插入操作
98. 验证二叉搜索树
450. 删除二叉搜索树中的节点
99. 恢复二叉搜索树
完全二叉树
222. 完全二叉树的节点个数
序列化和反序列化二叉树

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,125评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,293评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,054评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,077评论 1 291
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,096评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,062评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,988评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,817评论 0 273
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,266评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,486评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,646评论 1 347
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,375评论 5 342
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,974评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,621评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,642评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,538评论 2 352

推荐阅读更多精彩内容