STAy's Blog

落叶的一生，只为了归根么？

【算法】动态规划

发布于 2020-12-02 | 分类于 算法 、 动态规划 | 31分钟 | 6001字数

如果某一问题有很多重叠子问题。

动规中每一个状态一定是由上一个状态推导出来的，这一点区别于贪心。贪心没有推导状态，而是从局部直接选取最优的。

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

简单动规题

斐波那契数列

https://leetcode-cn.com/problems/fibonacci-number/

爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/

最小花费爬楼梯

https://leetcode-cn.com/problems/min-cost-climbing-stairs/submissions/

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp[1005];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= cost.size(); i ++ ) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()];
    }
};

不同路径

https://leetcode-cn.com/problems/unique-paths/

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[101][101];
        for (int i = 0; i <= m; i ++) {
            dp[0][i] = 0;
            dp[i][0] = 0;
        }
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (i == 1 && j == 1) 
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];

    }
};

不同路径2

https://leetcode-cn.com/problems/unique-paths-ii/

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        int dp[101][101];
        for (int i = 0; i <= m; i ++) {
            dp[0][i] = 0;
            dp[i][0] = 0;
        }
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (i == 0 && j == 0) 
                    dp[i + 1][j + 1] = 1;
                else if (obstacleGrid[i][j] == 1) 
                    dp[i + 1][j + 1] = 0;
                else if (i == 0 || obstacleGrid[i - 1][j] == 1)
                    dp[i + 1][j + 1] = dp[i + 1][j];
                else if (j == 0 || obstacleGrid[i][j - 1] == 1)
                    dp[i + 1][j + 1] = dp[i][j + 1];
                else
                    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j];
            }
        }
        return dp[m][n];
    }
};

整数拆分※

https://leetcode-cn.com/problems/integer-break/

class Solution {
public:
    int integerBreak(int n) {
        int dp[60]; // dp[i] 表示i拆分后乘积的最大值
        memset(dp, 0, sizeof(dp));
        dp[2] = 1;
        for (int i = 3; i <= n; i ++) {
            for (int j = 1; j < i - 1; j ++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
                // 对于i，将其拆分两个数-> j, (i-j)
                // 拆分成多个数-> j, dp[i-j]
                // 最大值可能是拆分成两个数，也可能拆分成多个数，例如3，可以拆分成1，2，也可以是1，1，1，显然1，2的乘积最大。
            }
        }
        return dp[n];
    }
};

不同的二叉搜索树※

https://leetcode-cn.com/problems/unique-binary-search-trees/submissions/

这道题有些难度，需要总结推理一下。

96.不同的二叉搜索树1

当n=3时：

  1. 当1作为根，那么其右子树的种类和n=2时的情况一样；
  2. 当2作为根，那么其左右子树的种类和n=1时的情况一样；
  3. 当3作为根，那么其左子树的种类和n=1时的情况一样。

所以当n=m时：

  1. 将1作为根，那么其右子树的种类和n=m-1时的情况一样；
  2. 将2作为根，那么其左子树的种类和n=1时的一样，右子树的种类和n=m-2时的一样，左右子树情况相乘；
  3. 将3作为根，那么其左子树的种类和n=2时的一样，右子树的种类和n=m-3时的一样，左右子树情况相乘；
  4. ...
  5. 将m作为根，那么其左子树的种类和n=m-1时的情况一样。

可以推出递推公式：

dp[n]=dp[n−1]∗dp[0]+dp[n−2]∗dp[1]+dp[n−3]∗dp[2]+...+dp[0]∗dp[n−1]dp[n] = dp[n-1]*dp[0] + dp[n-2]*dp[1] + dp[n-3]*dp[2] + ... +dp[0]*dp[n-1] 

class Solution {
public:
    int numTrees(int n) {
        int dp[20];
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[i - j] * dp[j - 1];
            }
        }
        return dp[n];
    }
};

背包问题

背包问题基本上搞懂01背包，完全背包就差不多够了，最多再加上一个完全背包，其他的背包问题都是竞赛级别的了。

416.分割等和子集1

01背包

https://www.acwing.com/problem/content/2/

01背包就是将1~n物品中若干个装进容量为W的背包中，每件物品的重量为weight[i]，价值为value[i]。

二维dp

dp[i][j]表示前i件装进背包容量为j的背包中的最大价值，可以有两个方向去推出dp[i][j]：

  • 不放当前第i个物品，即dp[i][j] = dp[i-1][j];
  • 放当前第i个物品，即dp[i][j] = dp[i-1][j-wight[i]] + value[i]，如果放第i个物品，那么需要为背包腾出wight[i]为位置，即j-wight[i]

所以递推公式为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

初始化：

  • dp[i][0] = 0
  • 当j<weight[0]，也就是当背包容量小于最小物品时，dp[0][j]=0
  • 当j>=weight[0]，dp[0][j] = value[0]
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1005;

int main() {
    int n, v;
    int dp[N][N];
    int weight[N];
    int value[N];
    memset(dp, 0, sizeof(dp));
    
    scanf("%d %d", &n, &v);
    for (int i = 0; i < n; i ++) {
        scanf("%d %d", &weight[i], &value[i]);
    }
    
    for (int j = weight[0]; j <= v; j ++) {
        dp[0][j] = value[0];
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= v; j++) {
            if(j >= weight[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n - 1][v];
}

一维dp

从二维dp的递推公式中可以看出每次迭代都与前一行有关，其实可以将i-1行叠加到i行，那么就可以只用一个数组。

一维dp[j]的含义时，容量为j的背包，最大价值是dp[j]。

此时递推公式：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])

初始化：如果所有的价值都是正数，那么可以全部初始化为0。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1005;

int main() {
    int n, v;
    int dp[N];
    int weight[N];
    int value[N];
    memset(dp, 0, sizeof(dp));
    
    scanf("%d %d", &n, &v);
    for (int i = 0; i < n; i ++) {
        scanf("%d %d", &weight[i], &value[i]);
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = v; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
        }
    }
    cout << dp[n - 1][v];
}



// go
package main

import "fmt"

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	var n, v int
	var weight, value []int
	var dp []int
	fmt.Scanf("%d %d", &n, &v)

	for i := 0; i < n; i++ {
		weight = append(weight, 0)
		value = append(value, 0)
		fmt.Scanf("%d %d", &weight[i], &value[i])
	}

	for i := 0; i <= v; i++ {
		dp = append(dp, 0)
	}

	for i := 0; i < n; i++ {
		for j := v; j >= weight[i]; j-- {
			dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
		}
	}
	fmt.Printf("%v\n", dp)
	fmt.Println(dp)
	fmt.Printf("%d\n", dp[v])
}

一维dp的迭代写法和二维dp的写法是不一样的，二维dp遍历的时候，背包容量是从小到大的，而一维dp遍历的时候，背包是从大到小的。这是因为倒序是为了保证物品i只被放入一次。

分割等和子集

https://leetcode-cn.com/problems/partition-equal-subset-sum/

这道题看似是回溯搜索问题，但其实是背包问题，问题可以转化为找到一个子集，该子集中元素的和为整个数组的和的一半，找子集的过程其实就是一个01背包问题，只不过每个元素的weight和value值相等，对于每个元素只有取和不取两个选择，背包容量就是sum/2。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        
        for (int i = 0; i < nums.size(); i ++) {
            sum += nums[i];
        }
        if(sum % 2 != 0) return false;
        
        vector<int> dp(sum / 2 + 1, 0);
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = sum / 2; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        
        if (dp[sum / 2] == sum / 2) 
            return true;
        
        return false;
    }
};

最后一块石头的重量 II

https://leetcode-cn.com/problems/last-stone-weight-ii/

这道题其实就是尽量让石头分成重量尽可能相近相同的两堆，这样两堆之间相撞之后剩下的石头最小，结果就是两堆的差值。

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func lastStoneWeightII(stones []int) int {
    var dp [3005] int
    var sum int = 0

    for i := 0; i < len(stones); i++ {
        sum += stones[i]
    }

    for i := 0; i < len(stones); i++ {
        for j := sum / 2; j >= stones[i]; j-- {
            dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
        }
    }

    return sum - dp[sum / 2] * 2
}

一和零

https://leetcode-cn.com/problems/ones-and-zeroes/

这道题其实是01背包问题，只不过是二维的01背包，可以想成有两个背包，每次选一个物品，两个背包都会减去相应的容量。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int dp[101][101];
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < strs.size(); i ++) {
            int zero = 0;
            for (int j = 0; j < strs[i].length(); j++) {
                if (strs[i][j] == '0') zero ++;
            }
            int one = strs[i].length() - zero;
            for (int j = m; j >= zero; j--) {
                for (int k = n; k >= one; k--) {
                    dp [j][k] = max(dp[j][k], dp[j - zero][k - one] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

目标和※

https://leetcode-cn.com/problems/target-sum/

假设加法的总和为x，那么减法对应的总和就是sum-x，所以要求x-(sum-x)=target，x = (target + sum) / 2，问题转化为了选择若干个数，和为x，其实转化为一个组合问题。

同时注意如果target + sum为奇数则没有解，target>sum也没有解。

对于所有组合问题，背包的递推：

dp[j] += dp[j-nums[i]]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此时没有方案
        if ((S + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (S + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

// 没完全懂

完全背包

完全背包问题与01背包的问题区别就是每件物品都可以有无限个。

遍历顺序变一下就好：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1005;

int main() {
    int n, v;
    int dp[N];
    int weight[N];
    int value[N];
    memset(dp, 0, sizeof(dp));
    
    scanf("%d %d", &n, &v);
    for (int i = 0; i < n; i ++) {
        scanf("%d %d", &weight[i], &value[i]);
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = weight[i]; j <= v; j++) { // 这里从小到大
            dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
        }
    }
    cout << dp[n - 1][v];
}

这两层for循环的内外层可以互换，结果没有什么区别。

但是通常题目都会变一变，比如装满背包可以有几种方法，这时候内外层互换就有区别了。

零钱兑换 II

https://leetcode-cn.com/problems/coin-change-2/

这是一道多重背包问题、然后转化为组合问题

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func change(amount int, coins []int) int {
    var dp [5005] int
    dp[0] = 1

    for i := 0; i < len(coins); i++ {
        for j := coins[i]; j <= amount; j++ {
            dp[j] += dp[j - coins[i]]
        }
    }
    return dp[amount]
}

这道题最后让求组合数，即选择物品是没有顺序的，所以外层必须为遍历物品。

如果内层遍历物品，每件物品需要被遍历多次，那么这个时候相当于每次的选择顺序都有了，满足条件的都会被记录下来，比如选1,2和选2,1都会被记录下来，而组合问题中这两种选择是一个答案。

所以遍历背包放在外层是一个组合问题，放在内层是一个排列问题。

组合总和Ⅳ

https://leetcode-cn.com/problems/combination-sum-iv/

这道题题目说是组合，但根据题目描述，可以看出这是一道排列题，并非我们常规认为的排列，而是需要满足题目要求，同时选择的顺序不同算作是多种答案。

因此需要将物品的遍历顺序放在内层循环。

func combinationSum4(nums []int, target int) int {
    var dp [1005] int
    dp[0] = 1
    
    for j := 0; j <= target; j++ {
        for i := 0; i < len(nums); i++ {
            if j >= nums[i] {
                dp[j] += dp[j - nums[i]]
            }
        }
    }
    return dp[target]
}

m阶爬楼梯

这道爬楼梯问题https://leetcode-cn.com/problems/min-cost-climbing-stairs/submissions/限制了每次只能跨1阶或2阶楼梯，那如果改成，每次可以跨1阶、2阶...m阶，可以有多少种爬楼梯的方法。

其实这就是一道完全背包问题，把1,2,3,4,...,m看成是物品的体积，楼顶就是背包容量，每个物品是可以重复选的，变成了一道考察排列的完全背包问题。同样的，需要把物品遍历放在内层循环。

零钱兑换

https://leetcode-cn.com/problems/coin-change/

每个物品不限次数，可以看出是完全背包问题，最终求出填满背包，需要最少的物品的数量，如果不能填满，则输出-1。

  • 定义dp[j]表示填满背包容量为j需要的最少物品数量。

  • dp[j]只有一个来源，即dp[j-coins[i]]，dp[j]要取所有dp[j-coins[i]]+1当中最小的，递推公式dp[j] = min(dp[j], dp[j-coins[i]] + 1)

  • 初始化：dp[j]要定义为一个最大的数，在这里定义为amount+1就已经够大了。

  • 遍历顺序：求钱币的最小数目，钱币有无顺序都无所谓。内外层互换也是可以的。

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func coinChange(coins []int, amount int) int {
    var dp [10005] int

    for i := 1; i <= amount; i++ {
        dp[i] = amount + 1
    }
    
    for j := 0; j <= amount; j++ {
        for i := 0; i < len(coins) ; i ++ {
            if j >= coins[i] {
                dp[j] = min(dp[j], dp[j - coins[i]] + 1)
            }
        }
    }

    if dp[amount] == amount + 1 {
        return -1
    }
    return dp[amount]
}

完全平方数

https://leetcode-cn.com/problems/perfect-squares/

和零钱兑换是一样的。

func min (x, y int) int {
    if x < y {
        return x
    }
    return y
}


func numSquares(n int) int {
    var dp [10005] int

    for i := 1; i <= n; i++ {
        dp[i] = n + 1
    }
    dp[1] = 1
    sqrtn := int(math.Sqrt(float64(n)))
    for i := 1; i < sqrtn + 1; i ++ {
        for j := 1; j <= n; j++ {
            if j >= i * i {
                dp[j] = min(dp[j], dp[j - i * i] + 1)
            }
        }
    }
    return dp[n]
}

单词拆分

https://leetcode-cn.com/problems/word-break/

go的切片操作把我绕晕了，这个就是遍历整个字符串。

dp[j]：表示前j字符是否可以被拆分成字典里出现过的单词。那么dp[j]可由所有dp[j - wordDict[i]]推得，只要有一个dp[j-wordDict[i]]为true，那么dp[j]就为true。

另外单词字典遍历必须在内层，因为如果在外层，意思就是选过的单词不能再被选了，是不符合完全背包的。

func wordBreak(s string, wordDict []string) bool {
    var dp [305]bool
    dp[0] = true

    for j := 1;  j<= len(s); j++ {
        for i := 0; i < len(wordDict); i++ {
            if j >= len(wordDict[i]) && s[j - len(wordDict[i]):j] == wordDict[i] {
                dp[j] = dp[j - len(wordDict[i])] || dp[j]
            }
        }
    }
    return dp[len(s)]
}

多重背包

多重背包就是每件物品加上了次数的限制，比如每件物品限制的次数也不一定，多重背包问题可以转换成01背包，就是把每件物品拆分开来。

打家劫舍

打家劫舍

https://leetcode-cn.com/problems/house-robber/

dp[i]：前i个房间最大的价值

dp[i]递推公式：对于第i个房间，如果选择偷，那么dp[i] = dp[i-2]+nums[i]，否则dp[i] = dp[i-1]，因此dp[i] = max(dp[i-1],dp[i-2]+nums[i])。

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}


func rob(nums []int) int {
    var dp [105] int
    dp[0] = nums[0]
    if len(nums) >= 2 {
        dp[1] = max(nums[0], nums[1])
    }
    for i := 2; i < len(nums); i++ {
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    }
    return dp[len(nums) - 1]
}

打家劫舍 II※

https://leetcode-cn.com/problems/house-robber-ii/

这道题是把首尾的房子连成了一个环，因此可以基于两种情况考虑：

  1. 不考虑第一个房子，从第二个开始
  2. 从第一个房子开始，但不考虑最后一个
func max (x, y int) int {
    if (x > y) {
        return x
    }
    return y
}
func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    var dp1 [105] int
    var dp2 [105] int
    dp1[0] = nums[0]
    dp2[1] = nums[1]
    if len(nums) > 1 {
        dp1[1] = max(nums[0], nums[1])
    }
    if len(nums) > 2 {
        dp2[2] = max(nums[1], nums[2])
    }
    for i := 2; i < len(nums); i++ {
        if i < len(nums) - 1 {
            dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i])
        }
        if i > 2 {
            dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i])
        }
    }
    return max(dp1[len(nums) - 2], dp2[len(nums) - 1])
}

打家劫舍Ⅲ(树状dp)※

https://leetcode-cn.com/problems/house-robber-iii/

对于树状的dp，首先需要遍历整个树，那么需要采用后续遍历，只有获取完子节点的dp数组之后，再决定当前节点的状态。

对于每个节点有两个状态，就是偷和不偷。如果偷，那么子节点就不可以偷了；如果不偷，那么就可以考虑偷子节点的，注意是考虑，并不是一定要偷，需要取子节点偷和不偷的最大值。

因此对于每个节点只需要返回两个值dp[2]就可以了，dp[0]表示不偷，dp[1]表示偷

  1. 不偷当前节点的最大值

    dp[0] = max(left.dp[0], left.dp[1]) + max(right.dp[0], right.dp[1])

  2. 偷当前节点的最大值

    dp[1] = root.val + left.dp[0] + right.dp[0]

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func max (x, y int) int {
    if x > y {
        return x
    }
    return y
}

// dp[0] 不偷 dp[1] 偷
func robTree(root *TreeNode) [2]int {
    if root == nil {
        return [2]int{0, 0}
    }
    var left, right, dp [2]int

    left = robTree(root.Left)
    right = robTree(root.Right)

    // 对于当前节点不偷，那么可以考虑偷左右孩子的，注意是考虑，不是一定偷
    dp[0] = max(left[0], left[1]) + max(right[0], right[1])
    // 如果偷，那么左右孩子的就不能偷了
    dp[1] = root.Val + left[0] + right[0]

    return dp
}

func rob(root *TreeNode) int {
    var dp [2]int = robTree(root)
    return max(dp[0], dp[1])
}

没有上司的舞会

https://www.acwing.com/problem/content/287/

和打家劫舍Ⅲ一样是树状DP，但是这道题是不再是二叉树，而是多叉树，但是方法还是不变，对于一个节点只有偷和不偷两个选择。

只不过这道题的输入需要自己构建....

package main

import "fmt"

type treeNode struct {
	Val int
	child []*treeNode
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func treeTrace(root *treeNode) [2]int {
	if root == nil {
		return [2]int{0, 0}
	}
	
	var dp [2]int
	for i := 0; i < len(root.child); i++ {
		tmp := treeTrace(root.child[i])
		dp[0] += max(tmp[0], tmp[1])
		dp[1] += tmp[0]
	}
	dp[1] += root.Val

	return dp
}

func main() {
	var n int
	var staffs []treeNode
	var flag [6005] int

	fmt.Scanf("%d", &n)

	for i := 0; i < n; i++ {
		var staff treeNode
		fmt.Scanf("%d", &staff.Val)
		staffs = append(staffs, staff)
	}

	for i := 0; i < n - 1; i++ {
		var l, k int
		fmt.Scanf("%d %d", &l, &k)
		flag[l] = 1
		staffs[k - 1].child = append(staffs[k - 1].child, &staffs[l - 1])
	}

	var root int
	for i := 1; i <= n; i++ {
		if flag[i] == 0 {
			root = i
			break
		}
	}
	var res = treeTrace(&staffs[root - 1])

	fmt.Println(max(res[0], res[1]))

}

子序列问题

最长递增子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func lengthOfLIS(nums []int) int {
    var dp [2505]int
    var res int = 1
    for i := 0; i < len(nums); i++ {
        dp[i] = 1
    }

    for i := 0; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j] + 1)
                if res < dp[i] {
                    res = dp[i]
                }
            }
        }
    }

    return res
}

最长连续递增子序列

https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}


func findLengthOfLCIS(nums []int) int {
    var dp [10005]int
    var res int = 1
    for i := 0; i < len(nums); i++ {
        dp[i] = 1
    }

    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i - 1] {
            dp[i] = dp[i - 1] + 1
        }
        if res < dp[i] {
            res = dp[i]
        }
    }

    return res
}

最长公共子序列

很显然dp[i][j]的定义为text1的前i个字符和text2的前j个字符的最长公共子序列的字符个数，递推公式：

  1. 如果text1[i] == text[j]：dp[i][j] = dp[i-1][j-1] + 1
  2. 如果text1[i] != text[j]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

https://leetcode-cn.com/problems/longest-common-subsequence/

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func longestCommonSubsequence(text1 string, text2 string) int {
    var dp [1005][1005]int

    for i := 0; i < len(text1); i++ {
        for j := 0; j < len(text2); j++ {
            if text1[i] == text2[j] {
                dp[i + 1][j + 1] = dp [i][j] + 1
            } else {
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
            }
        }
    }
    
    return dp[len(text1)][len(text2)]
}

最长连续公共子序列

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func findLength(nums1 []int, nums2 []int) int {
    var dp[1005][1005] int
    var res int = 0
    for i := 0; i < len(nums1); i++ {
        for j := 0; j < len(nums2); j++ {
            if nums1[i] == nums2[j] {
                dp[i+1][j+1] = dp[i][j] + 1
            }
            if res < dp[i+1][j+1] {
                res = dp[i+1][j+1]
            }
        }
    }

    return res

}

最短编辑距离

https://www.acwing.com/problem/content/904/

  1. 添加一个字母之后变得相同，说明没有添加前a的前i个已经和b的前j-1个已经相同
    即 ： dp[i][j] = dp[i][j-1] + 1
  2. 删除该字母之后变得相同，说明没有删除前a中前i-1已经和b的前j个已经相同
    即 ： dp[i][j] = dp[i-1][j] + 1
  3. 替换说明对应结尾字母不同，则看倒数第二个
    即： dp[i][j] = dp[i-1][j-1] + 1
  4. 两字符相等：dp[i][j] = dp[i-1][j-1]
package main

import "fmt"

func min(x, y, z int) int {
    if x <= y && x <= z {
        return x
    } else if y <= x && y <= z {
        return y
    } else {
        return z
    }
}

func main() {
    var m, n int
    var str1, str2 string
    var dp [1005][1005]int
    
    fmt.Scanf("%d", &n)
    fmt.Scanf("%s", &str1)
    fmt.Scanf("%d", &m)
    fmt.Scanf("%s", &str2)

    for i := 1; i <= m; i++ {
        dp[0][i] = i
    }

    for i := 1; i <= n; i++ {
        dp[i][0] = i
    }
    
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if str1[i] == str2[j] {
                dp[i + 1][j + 1] = dp[i][j]
            } else {
                dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j], dp[i][j]) + 1
            }
        }
    }
    fmt.Println(dp[n][m])
}

编辑距离

https://www.acwing.com/problem/content/901/

和上题没什么太大差别。

package main

import "fmt"

func min(x, y, z int) int {
	if x <= y && x <= z {
		return x
	} else if y <= x && y <= z {
		return y
	} else {
		return z
	}
}

func main() {
	var n, m int
	var str [1005]string

	fmt.Scanf("%d %d", &n, &m)

	for i := 0; i < n; i++ {
		fmt.Scanf("%s", &str[i])
	}
	for i := 0; i < m; i++ {
		var cnt, cntn int
		var pat string
		fmt.Scanf("%s %d", &pat, &cntn)
        
		for j := 0; j < n; j ++ {
			var dp [15][15]int
			for k := 1; k <= 11; k ++ {
				dp[k][0] = k
				dp[0][k] = k
			}
			
			for l := 0; l < len(str[j]); l++ {
				for o := 0; o < len(pat); o++ {
					if str[j][l] == pat[o] {
						dp[l+1][o+1] = dp[l][o]
					} else {
						dp[l+1][o+1] = min(dp[l][o+1], dp[l+1][o], dp[l][o]) + 1
					}
				}z
			}
			if cntn >= dp[len(str[j])][len(pat)] {
				cnt ++
			}
		}
		fmt.Println(cnt)
	}
}

回文子串(区间DP)

https://leetcode-cn.com/problems/palindromic-substrings/

这道题可以定义dp[i]表示前i个字符的回文子串的数目。
那么下来包括判断字串是否是回文一共是三重循环了，能通过。

func palindrome(s string) bool {
    for i := 0; i < len(s); i++ {
        if s[i] != s[len(s) - i - 1] {
            return false
        }
    }
    return true
}

func countSubstrings(s string) int {

    var dp [1005]int

    for i := 1; i <= len(s); i++ {
        var cnt int = 0
        for j := 0; j < i; j++ {
            if palindrome(s[j:i]) {
                cnt ++
            }
        }
        dp[i] = dp[i-1] + cnt
    }

    return dp[len(s)]

}

其实这道题更好的做法是定义dp[i][j]表示为s[i:j]是不是回文，因此是一个区间，外层循环是区间的窗口大小，内层是通过滑动窗口。
只有s[i] == s[j] && (i == 1 || dp[i+1][j-1])时，dp[i][j] = true。

class Solution {
public:
    int countSubstrings(string s) {
        bool dp[1001][1001]={0};
        int res=s.length();
        for(int i=0;i<s.length();i++)
            dp[i][i]=1;        
        for(int i=1;i<=s.length();i++)
        {
            for(int j=0;j+i<s.length();j++)
            {
                if(s[j]==s[j+i] && (j==j+i || j==i+j-1 || dp[j+1][i+j-1]))
                {
                    // cout<<j<<" "<<i+j<<endl;
                    dp[j][i+j]=1;
                    res++;
                }
            }
        }
        return res;
    }
};

闫氏dp分析法https://www.cnblogs.com/IzayoiMiku/p/13635809.html

# 算法 # 动态规划
【linux】文件系统与操作 上一篇
【算法】查找 下一篇
0%