算法小抄

2021-01-17 本文已影响0人 upup果

动态规划

动态规划三要素

重叠子问题：重复计算
最优子结构：通过子问题的最值得到原问题的最值

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

#初始化 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 函数/数组的定义。

基本动态规划：一维

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

基本动态规划：二维

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

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];

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);

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