数据结构与算法-labuladong-第二章

oublie included in 数据结构与算法

2023-02-04 2263 words 5 minutes

Contents

本系列笔记为作者在跟随labuladong的算法小抄学习的时候结合golang做的笔记。感谢东哥。另外根据东哥对算法的分类法，将自己平时记的笔记也写到这里面。

第二章：手把手刷动态规划

动态规划解题套路框架

不要迷恋那些看起来很牛逼，代码很短小的解法思路，最好是稳一点，采取可解释性最好，最容易推广的解法思路。

动态规划问题的一般形式就是求最值。

求解动态规划的核心问题是穷举。

详见第零章

编辑距离

leetcode 72 编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数

一次操作可以插入，删除和替换1个字符

思路：动态规划

首先定义basecase，当一个字符串长度为0时，直接把另一个字符串的每个字符插入该字符或者将另一个字符的每个字符删除即可。
定义状态，要想到达basecase，只能在长度上进行缩减，两个单词的长度分别用i，j表示，dp表为一个二位数组且长度分别为len(word1)+1，len(word2)+1，basecase表示dp[i][0]=i,dp[0][j]=j。
然后定义选择，虽然说一次操作可以插入删除和替换，但是其实插入和删除可以合并位插入，因为删除word1的一个字符就等价于插入word2一个字符。所以从父问题到子问题可选择的操作有插入1个字符，替换一个字符和不操作。
另外根据word1[i]和word2[j]是否相等将问题dp[i,j]的状态转移方程分为两种情况：

当word1[i]==word2[j]时：我们可能是从子问题dp[i-1][j]选择插入一个字符得到dp[i][j]问题的答案，从子问题dp[i][j-1]选择插入一个字符得到dp[i][j]问题的答案，以及从子问题dp[i-1][j-1]不操作得到dp[i][j]问题的答案，所以dp[i][j]=min(dp[i][j−1]+1,dp[i−1][j]+1,dp[i−1][j−1])
当word1[i]!=word2[j]时，前两种选择和上面一样，但是这里不操作就不行了，可以在子问题dp[i-1][j-1]的基础上替换一个字符得到dp[i][j]的答案，所以dp[i][j]=1+min(dp[i][j−1],dp[i−1][j],dp[i−1][j−1])

最后根据状态转移方程写出自顶向下或者自底向上的解题代码

自顶向下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


func minDistance(word1 string, word2 string) int {
    l1,l2:=len(word1),len(word2)
    dp:=make([][]int,l1+1)
    
    for i:=0;i<len(dp);i++{
        dp[i]=make([]int,l2+1)
        for j:=0;j<l2+1;j++{
            dp[i][j]=-1
        }
        dp[i][0]=i
    }
    for j:=0;j<len(dp[0]);j++{
        dp[0][j]=j
    }

    var dpfun func (i,j int) (int)
    dpfun = func (i,j int) (int){
        if dp[i][j]!=-1{return dp[i][j]}
        if word1[i-1]==word2[j-1]{
            dp[i][j]=Min(dpfun(i-1,j-1),dpfun(i-1,j)+1,dpfun(i,j-1)+1)
        }else {
            dp[i][j]=Min(dpfun(i-1,j-1)+1,dpfun(i-1,j)+1,dpfun(i,j-1)+1)
        }
        return dp[i][j]
    }

    return dpfun(l1,l2)
}


func Min(s ...int)int{
    tmp:=s[0]
    for _,v:=range s{
        if tmp>v{tmp=v}
    }
    return tmp
}

空间压缩

如果转移方程右边的某一维(i)的值只和i或i相邻的值（i和i-k或者i和i+k）相关，那么就能把其占有的空间优化掉

通常只能优化一个维度

i和i-k则从小到大遍历，i和i+k则从大到小遍历

比如:dp[i][j]=dp[i][j-w[i-1]]

优化为:dp[j]=dp[j-w[i-1]]

背包问题

01背包

每个物品只放一次，求容量w能放下的最大价值

状态定义:dp[i][j]为仅使用前i个物品（dp中的索引为i，对应物品索引为i-1），容量为j时能获取的最大价值，值为数值类型

basecase:dp[…][0]=0，dp[0][…]=0

转移方程：把第i个物品装入或不装入

dp[i][j]=max(dp[i-1][j],dp[i][j-w[i-1]]+v[i-1]),j-w[i-1]>=0 dp[i-1][j],j-w[i-1]<0，无法装入

空间优化:i从小到大遍历

dp[j]=max(dp[j],dp[j-w[i-1]]+v[i-1]),j-w[i-1]>=0 dp[j],j-w[i-1]<0

下面优化掉

dp[j]=max(dp[j],dp[j-w[i-1]]+v[i-1]),j-w[i-1]>=0

子集背包：每个物品只能放一次，要求把背包装满

每个物品只放一次，求是否能完全放满背包

状态定义:dp[i][j]为使用前i个物品能否放满背包，值为bool类型

basecase:dp[…][0]=true，dp[0][…]=false

转移方程：和01背包一样

1
2


dp[i][j]=dp[i-1][j]||dp[i][j-w[i-1]],j-w[i-1]>=0
         dp[i-1][j],j-w[i-1]<0

空间优化：i从小到大遍历

1
2


dp[j]=dp[j]||dp[j-w[i-1],j-w[i-1]>=0
      dp[j],j-w[i-1]<0

优化掉下面这个就变成了

1

dp[j]=dp[j]||dp[j-w[i-1],j-w[i-1]>=0

完全背包

每个物品都可以放无限次，有多少种填满背包的方法

例子：518. 零钱兑换 II

状态定义:dp[i][j]为只使用前i个物品，容量为j时填满背包的方法有多少个

basecase:dp[0][…]=0,dp[…][0]=1

转移方程:和01背包一样

1
2


dp[i][j]=dp[i-1][j]+dp[i][j-w[i-1]],j-w[i-1]>=0
         dp[i-1][j],j-w[i-1]<0

空间优化：i从小到大遍历

1

dp[j]=dp[j]+dp[j-w[i-i]],j-w[i-1]>=0

博弈类dp

486. 预测赢家

877. 石子游戏

定义 dp 数组的含义:

dp[i][j].fir = x 表示，对于 piles[i…j] 这部分石头堆，先手能获得的最高分数为 x。
dp[i][j].sec = y 表示，对于 piles[i…j] 这部分石头堆，后手能获得的最高分数为 y。

选择

先手状态：选择最左边的那堆石头，或者选择最右边的那堆石头
后手状态：先手选择后剩下石头堆的先手状态

1
2
3
4
5
6
7


dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec)
dp[i][j].fir = max(     选择最左边的石头堆     ,     选择最右边的石头堆      )

if 先手选择左边:
    dp[i][j].sec = dp[i+1][j].fir
if 先手选择右边:
    dp[i][j].sec = dp[i][j-1].fir

由于状态转移方程右边都是i+1所以i得从大到小遍历，j-1所以j得从小到大遍历

数位DP

CSDN unique_pursuit

给定一个闭区间[l,r]，让你求这个区间中满足某种条件的数的总数

求[0,r]满足条件的数的总数，从最高位逐位枚举，对于第n位（十进制或二进制等），r的数字位an，那么分两种情况[0,an-1]和an（有时候0也需要作为额外的特殊情况，这样就是3个特殊情况了）。[0,an-1]可以直接得到结果，an则继续细分，当第n位取an时，得到子问题第n-1位取值
求出[0,r]的结果之后，使用同样的方式求[0,l-1]的结果，然后相减就是最后的结果

通常设置memo的大小为[位数][可取值（一般为10）]

然后有一个dp(i)函数求第i位所在位置的答案(可以是递归也可以是递推)

数位dp使用strconv.Atoi()以及strconv.Itoa()结合字符串连接操作可以简化很多问题