Day51 | 动态规划 ：区间DP 最长回文子序列&&多边形三角部分的最低得分

动态规划应该如何学习？-CSDN博客

本次题解参考自灵神的做法，大家也多多支持灵神的题解

区间 DP：最长回文子序列【基础算法精讲 22】_哔哩哔哩_bilibili

动态规划学习：

1.思考回溯法（深度优先遍历）怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的，怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

image-20241128145120008

516.最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）

思路分析（子问题）:

1.s和反转s求它俩的最长公共子序列

2.直接求

还是选或不选的思路

dfs(i,j)表示从i到j这段里面的最长回文子序列的长度

那就是看选或不选s[i]和s[j]

三种情况

选s[i]和s[j]

选s[i]不选s[j]

不选s[i]选s[j]

如果s[i]==s[j]

1
dfs(i,j)=dfs(i+1,j-1)+2;

如果s[i]!=s[j]，那就是两个里面选个最大值

1
dfs(i,j)=max(dfs(i+1,j),dfs(i,j-1));

image-20241128151615158

递归边界

1
dfs(i,j) i>j

说明i和j中间没有字符，是空串，返回0

1
dfs(i,j) i==j

说明i到j只有一个字符，这个字符组成一个子序列，长度为1，并且也是回文的，返回1

1.回溯 DFS

1.返回值和参数

dfs(i,j)表示从i到j这段里面的最长回文子序列的长度

1
int dfs(int i,int j,string &s)

2.终止条件

对应递归边界

1
2
3
4
if(i>j)
    return 0;
if(i==j)
    return 1;

3.本层逻辑

1
2
3
4
if(s[i]==s[j])
    return dfs(i+1,j-1,s)+2;
else
    return max(dfs(i+1,j,s),dfs(i,j-1,s));

完整代码：

当然，这是超时的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int dfs(int i,int j,string &s)
    {
        if(i>j)
            return 0;
        if(i==j)
            return 1;
        if(s[i]==s[j])
            return dfs(i+1,j-1,s)+2;
        else
            return max(dfs(i+1,j,s),dfs(i,j-1,s));
    }
    int longestPalindromeSubseq(string s) {
        
        return dfs(0,s.size()-1,s);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//lambda
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        function<int(int,int)> dfs=[&](int i,int j)->int{
            if(i>j)
            return 0;
            if(i==j)
                return 1;
            if(s[i]==s[j])
                return dfs(i+1,j-1)+2;
            else
                return max(dfs(i+1,j),dfs(i,j-1));
        };
        return dfs(0,s.size()-1);
    }
};

2.记忆化搜索

就是搞一个哈希表dp，全都初始化为-1，每次返回前给哈希表dp赋值，碰到不是-1的那就是算过的，那就直接返回计算过的结果，不需要再次递归了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int dfs(int i,int j,string &s,vector<vector<int>> &dp)
    {
        if(i>j)
            return 0;
        if(i==j)
            return 1;
        if(dp[i][j]!=-1)
            return dp[i][j];
        if(s[i]==s[j])
            return dp[i][j]=dfs(i+1,j-1,s,dp)+2;
        else
            return dp[i][j]=max(dfs(i+1,j,s,dp),dfs(i,j-1,s,dp));
    }
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),-1));
        return dfs(0,s.size()-1,s,dp);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//lambda
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),-1));
        function<int(int,int)> dfs=[&](int i,int j)->int{
            if(i>j)
            return 0;
            if(i==j)
                return 1;
            if(dp[i][j]!=-1)
                return dp[i][j];
            if(s[i]==s[j])
                return dp[i][j]=dfs(i+1,j-1)+2;
            else
                return dp[i][j]=max(dfs(i+1,j),dfs(i,j-1));
        };
        return dfs(0,s.size()-1);
    }
};

3.1:1翻译为动态规划

1.确定dp数组以及下标的含义

dp[i][j]就是dfs(I,j)

2.确定递推公式

和dfs中也是对应的

1
2
3
4
if(s[i]==s[j])  
                dp[i][j]=dp[i+1][j-1]+2;
            else
                dp[i][j]=max(dp[i+1][j],dp[i][j-1]);

3.dp数组如何初始化

都初始化为0即可

1
2
3
vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
for(int i=0;i<s.size();i++)
	dp[i][i]=1;

4.确定遍历顺序

i由i+1推导来的，所以i需要倒序遍历

j由j-1推导来的，所以j需要正序遍历

为什么j从i+1开始？

因为j<i的时候都是空串，我们在递归中直接返回的0，这里咱们初始化的时候已经做了这个工作，就不需要再管了

1
2
3
4
5
6
for(int i=s.size()-1;i>=0;i--)
          for(int j=i+1;j<s.size();j++)
              if(s[i]==s[j])  
                  dp[i][j]=dp[i+1][j-1]+2;
              else
                  dp[i][j]=max(dp[i+1][j],dp[i][j-1]);

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
        for(int i=0;i<s.size();i++)
            dp[i][i]=1;
        for(int i=s.size()-1;i>=0;i--)
            for(int j=i+1;j<s.size();j++)
                if(s[i]==s[j])  
                    dp[i][j]=dp[i+1][j-1]+2;
                else
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
        return dp[0][s.size()-1];
    }
};

1039.多边形三角剖分的最低得分

1039. 多边形三角剖分的最低得分 - 力扣（LeetCode）

区间 DP：最长回文子序列【基础算法精讲 22】_哔哩哔哩_bilibili

笔者就贴一下代码，思路啥的大家看灵神讲吧

1.回溯dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int dfs(int i,int j,vector<int>& values)
    {
        if(i+1==j)
            return 0;
        int res=INT_MAX;
        for(int k=i+1;k<j;k++)
            res=min(res,dfs(i,k,values)+dfs(k,j,values)+values[i]*values[j]*values[k]);
        return res;
    }
    int minScoreTriangulation(vector<int>& values) {
        return dfs(0,values.size()-1,values);
    }
};

2.记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int dfs(int i,int j,vector<int>& values,vector<vector<int>>& dp)
    {
        if(i+1==j)
            return 0;
        int res=INT_MAX;
        if(dp[i][j]!=-1)
            return dp[i][j];
        for(int k=i+1;k<j;k++)
            res=min(res,dfs(i,k,values,dp)+dfs(k,j,values,dp)+values[i]*values[j]*values[k]);
        return dp[i][j]=res;
    }
    int minScoreTriangulation(vector<int>& values) {
        vector<vector<int>> dp(values.size(),vector<int>(values.size(),-1));
        return dfs(0,values.size()-1,values,dp);
    }
};

3.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minScoreTriangulation(vector<int>& v) {
        int n = v.size();
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                f[i][j] = INT_MAX;
                for (int k = i + 1; k < j; k++) {
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + v[i] * v[j] * v[k]);
                }
            }
        }
        return f[0][n - 1];
    }
};