区间DP

数据结构与算法

发布日期: 2020-12-25

看到题有什么特点可以用区间dp?

提示1


时间复杂度可以O(n^2)-数组长度≤1000

提示2


状态转移与两端有关

区间dp应该怎么思考

提示1


递归回溯型思考

提示2


类似递归回溯
左右子区间f[i][k]和f[k][j]已经做完了,再考虑当前位置k和左右两个端点i,j

回文系列

leetcode 5最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。

示例：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

思路

状态表示

$f[i][j]$：$s[i:j]$是否是回文串
状态转移

$f[i][j]=s[i]==s[j]\&\&f[i+1][j-1]$

动态维护最长的$string$

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>>f(n,vector<int>(n,0));
        string res;
        int l,r,maxi;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(j-i+1>2&&s[i]==s[j])f[i][j]=f[i+1][j-1];
                else f[i][j]=s[i]==s[j]?1:0;
                if(f[i][j]==1&&j-i+1>res.size())
                {
                    res=s.substr(i,j-i+1);
                }        
            }
        }
        return res;
    }
};

leetcode 516 最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例:

输入:

"bbbab"
输出:

4
一个可能的最长回文子序列为 "bbbb"。

输入:

"cbbd"
输出:
2
一个可能的最长回文子序列为 "bb"。

数据范围：

1 <= s.length <= 1000
s 只包含小写英文字母

思路

状态表示

$f[i][j]$:$s[i:j]$中最长子序列长度
状态转移

$f[i][j]=max(f[i+1][j-1]+2 \quad if \quad s[i]==s[j],f[i+1][j],f[i][j-1])$

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>>f(n,vector<int>(n,1));
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(j-i+1>2)
                {
                    if(s[i]==s[j])
                        f[i][j]=max(f[i][j],f[i+1][j-1]+2);
                    f[i][j] = max(f[i][j],max(f[i+1][j],f[i][j-1]));
                }
                else f[i][j]=s[i]==s[j]?j-i+1:1;
            }
        }
        return f[0][n-1];
    }
};

leetcode 647回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例：

输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

数据范围

输入的字符串长度不会超过 1000 。

思路

状态表示

$f[i][j]$：$s[i:j]$是否是回文串
状态压缩

$f[i][j]=s[i]==s[j]\&\&f[i+1][j-1]$
当$f[i][j]=true$时$res++$

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.size();
        vector<vector<int>> f(n,vector<int>(n,0));
        int res=0;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(j-i+1>2&&s[i]==s[j])f[i][j]=f[i+1][j-1];
                else f[i][j]=s[i]==s[j]?1:0;
                if(f[i][j])res++;
            }
        }
        return res;
    }
};

leetcode 730 统计不同回文子序列

给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。

通过从 S 中删除 0 个或多个字符来获得子序列。

如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。

如果对于某个$i，A_i != B_i$，那么$A_1, A_2, …$ 和$B_1, B_2, …$ 这两个字符序列是不同的。

示例：

输入：
S = 'bccb'
输出：6
解释：
6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。

输入：
`S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'`
输出：`104860361`
解释：
共有 `3104860382` 个不同的非空回文子序列，对 `10^9 + 7` 取模为 `104860361`。

数据范围：

字符串S的长度将在[1, 1000]范围内。
每个字符S[i]将会是集合{'a', 'b', 'c', 'd'}中的某一个。

思路

状态表示

$f[i][j]$表示下标区间是$[i, j]$范围内的不同的回文子序列个数

状态转移

如果$S[i] == S[j]$:

$f[i][j] = 2 * f[i+1][j-1] + 2$

乘以2是内部的不同回文个数本身$f[i+1][j-1]$和套上左右边界两个字符后的不同回文个数$f[i+1][j-1]$

加上2是边界上两个相同字符组合起来可以形成长度是1和长度是2的两个不同的回文

但是还要分类讨论区间$[i+1,j-1]$有几个等于$S[i]$的字符
- $[i+1,j-1]$有1个等于$S[i]$的字符
  
  $f[i][j] = 2 f[i+1][j-1] + 1$
  则此时加上的2里长度是1的$S[i]$在计算$f[i+1][j-1]$的时候已经计算过了,*所以+2变成+1
- $[i+1,j-1]$有2个等于$S[i]$的字符
  
  $f[i][j] = 2 * f[i+1][j-1] - f[l+1][r-1]$
  
  则此时加上的2里长度是1的S[i]和长度是2的在计算f[i+1][j-1]的时候已经计算过了所以+2变成+0
  
  同时分别从左$i+1$和右$j-1$找到第一个等于$S[i]$的索引$l$和$r$
  
  可以发现$S[l+1:r-1]$与$S[l]及S[r]$构成的所有情况会和$S[l+1:r-1]$与$S[i]及S[j]$构成的所有情况重复
  
  所以减去$S[l+1:r-1]$与$S[i]和S[j]$构成的情况$f[l+1][r-1]$

如果$S[i] != S[j]$:

容斥原理,此时两端无法同时参与构成回文子序列,则$[i:j]$的所有可能数$cnt[i:j]=cnt([i:j-1]\cup[i+1:j])=cnt[i:j-1]+cnt[i+1:j]-cnt([i:j-1]\cap[i+1:j])$

$f[i][j] = f[i+1][j] + f[i][j-1] - f[i+1][j-1]$

class Solution {
public:
    int countPalindromicSubsequences(string s) {
        int n = s.size();
        vector<vector<int>> f(n,vector<int>(n,0));
        for(int i=0;i<n;i++)f[i][i]=1;
        const int mod = 1e9+7;
        for(int i=n-2;i>=0;i--)
        {
            for(int j=i+1;j<n;j++)
            {
                if(s[i]!=s[j])f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1];
                else
                {
                    f[i][j] = f[i+1][j-1]*2+2;
                    int l=i+1,r=j-1;
                    while(l<=r&&s[l]!=s[i])l++;
                    while(l<=r&&s[r]!=s[i])r--;
                    // 第2.1种情况 中间有1个s[i]
                    if(l==r)f[i][j]--;
                    // 第2.2种情况 中间有2个s[i]
                    else if(l<r)f[i][j] -=2+f[l+1][r-1];
                }
                f[i][j]=(f[i][j]>=0)?f[i][j]%mod:f[i][j]+mod;
            }
        }
        return f[0][n-1];
    }
};

leetcode 1147 段式回文

段式回文其实与一般回文类似，只不过是最小的单位是一段字符而不是单个字母。

举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把"volvo" 分为 "vo"、"l"、"vo" 三段，则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。

给你一个字符串text，在确保它满足段式回文的前提下，请你返回段的最大数量k。

如果段的最大数量为k，那么存在满足以下条件的$a_1, a_2, …, a_k$：

每个$a_i$都是一个非空字符串；
将这些字符串首位相连的结果$a_1 + a_2 + … + a_k$和原始字符串$text$相同；
对于所有$1 <= i <= k$，都有$a_i = a_{k+1 - i}$。

示例：

输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

输入：text = "merchant"
输出：1
解释：我们可以把字符串拆分成 "(merchant)"。

输入：text = "antaprezatepzapreanta"
输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。

输入：text = "aaa"
输出：3
解释：我们可以把字符串拆分成 "(a)(a)(a)"。

数据范围：

text仅由小写英文字符组成。
1 <= text.length <= 1000

思路

贪心的取更小的匹配串证明

假如我们当前没有选更短的R1而是等到更长的B1才加入， 则因为需要囊括所有位置，所以B1又需要包括R1 ，那么很明显选R1是比B1好的

class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.size();
        if(n==0)return 0;
        for(int i=1;i<=n/2;i++)
        {
            if(text.substr(0,i)==text.substr(n-i,i))
            {
                return 2+longestDecomposition(text.substr(i,n-2*i));
            }
        }
        return 1;
    }
};

leetcode 1312 让字符串成为回文串的最少插入次数

给你一个字符串s，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让s成为回文串的最少操作次数。

「回文串」是正读和反读都相同的字符串。

示例

输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

输入：s = "g"
输出：0

输入：s = "no"
输出：1

提示：

1 <= s.length <= 500
s中所有字符都是小写字母。

思路

本题属于516最长回文子序列的子题，求的就是不为最长回文子序列的字符个数，所以我们只需要用字符串长度$n$减去最长回文子序列的长度$f[0][n-1]$就是最少插入次数了。

状态表示

$f[i][j]$:$s[i:j]$中最长子序列长度
状态转移

$f[i][j]=max(f[i+1][j-1]+2 \quad if \quad s[i]==s[j],f[i+1][j],f[i][j-1])$

class Solution {
public:
    int minInsertions(string s) {
        int n=s.size();
        vector<vector<int>> f(n,vector<int>(n,0));
        for(int i=n-1;i>=0;i--)
        {
            f[i][i]=1;
            for(int j=i+1;j<n;j++)
            {
                if(s[i]==s[j])f[i][j]=f[i+1][j-1]+2;
                f[i][j] = max(f[i][j],max(f[i+1][j],f[i][j-1]));
            }
        }
        return n-f[0][n-1];
    }
};

其他区间dp

leetcode 312 戳气球

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

数据范围

你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例

输入: [3,1,5,8]
输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

思路

状态表示
$f[i][j]$表示区间$[i,j]$气球戳完的最多硬币数
状态转移

遍历$k\in [i,j]$
假设当前$[i,j]$的子区间$[i,k]$$[k,j]$都已经戳完了,则只剩下第k个气球没戳了

$f[i][j] = max(f[i][k]+f[k][j]+nums[i]nums[k]nums[j]$

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        const int N=510;
        int f[N][N];
        int a[N];
        memset(f,0,sizeof f);
        memset(a,0,sizeof a);
        for(int i=0;i<n;i++)
        {
            a[i+1]=nums[i];
        }
        a[0]=a[n+1]=1;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i+2;j<=n+1;j++)
            {
                for(int k=i+1;k<j;k++)
                {
                    int tot = a[i]*a[k]*a[j];
                    tot+=f[i][k]+f[k][j];
                    f[i][j] = max(f[i][j],tot);
                }
            }
        }
        return f[0][n+1];
    }
};

leetcode 471 编码最短长度的字符串

给定一个非空字符串，将其编码为具有最短长度的字符串。

编码规则是：k[encoded_string]，其中在方括号 encoded_string 中的内容重复 k 次。

k 为正整数
如果编码的过程不能使字符串缩短，则不要对其进行编码。如果有多种编码方式，返回任意一种即可

示例

输入：s = "aaa"
输出："aaa"
解释：无法将其编码为更短的字符串，因此不进行编码。

数据范围

1 <= s.length <= 150
s 由小写英文字母组成

思路

状态表示
$f[i][j]$: 区间$[i,j]$中最短的字符串表示
状态转移
$f[i][j] = minlength(f[i][j],f[i][k]+f[k+1][j])$
$k$个重复通过leetcode459重复的子字符串中实现

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.size();
    }
};

class Solution {
public:
    string encode(string s) {
        int n = s.size();
        vector<vector<string>> f(n,vector<string>(n,""));
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                f[i][j] = findrep(s,i,j,f);
                if(j-i+1>4)
                {
                    for(int k=i;k<j;k++)
                    {
                        string split = f[i][k]+f[k+1][j];
                        if(f[i][j].size()>split.size()) f[i][j] = split;
                    }
                }
            }
        }
        return f[0][n-1];
    }
    string findrep(string s,int i,int j,vector<vector<string>> f)
    {
        s = s.substr(i,j-i+1);
        if(s.size()<5)return s;
        int p = (s+s).find(s,1);
        if(p!=s.size())
        {
            int cnt = s.size()/p;
            return to_string(cnt)+"["+f[i][i+p-1]+"]";
        }
        return s;
    }
};

leetcode 546 移除盒子

给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。
当你将所有盒子都去掉之后，求你能获得的最大积分和。

示例

输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 分) 
----> [1, 3, 3, 3, 1] (1*1=1 分) 
----> [1, 1] (3*3=9 分) 
----> [] (2*2=4 分)

数据范围

1 <= boxes.length <= 100
1 <= boxes[i] <= 100

思路

状态表示

$f[l][r][k]$表示移除区间 $[l,r]$ 的元素 $a_l, a_{l + 1}, a_{l + 2} \cdots a_r$
加上该区间右边等于 $a_{r}$的 $k$ 个元素组成的这个序列的最大积分。
状态转移
1 ：直接把相邻相同的全部移除

{[6,3,6,5,6],7,6,6,8,6}，删除后面的四个 6，再删除前面的这个区间，这样获得的分数为 f(1, 4, 0) + 4^2
2 ：把不相邻的合并后一起移除，当然在合并前，把中间破环他们相邻的所有盒子要移除

{[6,3,6],[5],6,7,6,6,8,6}，删除一个单独的 $a_4$(即5)，分数是 f(4,4,0)；然后问题就变成了删除区间 [1,3] 以及这个区间后面和 $a_3$
相同的 4 个数，分数是f(1,3,4)；这样获得的分数是 f(1, 3, 4) + f(4, 4, 0)

{[6],[3,6,5],6,7,6,6,8,6}，删除 $a_2$、$a_3$、$a_4$
，因为与$a_4 = 5$的数在后面没有,所以分数为 f(2, 4, 0)；之后再删除区间 [1,1] 和这个区间后和 $a_1$
相同的 4 个数，分数是 f(1,1,4)；这样获得的分数是 f(1,1,4)+f(2,4,0)

$f(l,r,k)=max(f(l,r−1,0)+(k+1)^2, \max_{i=l}^{r−1}{[f(l,i,k+1)+f(i+1,r−1,0)]×ϵ(a_i ==a_r )})$

class Solution {
public:
    int f[110][110][110];
    int removeBoxes(vector<int>& boxes) {
        memset(f,0,sizeof f);
        return dp(boxes,0,boxes.size()-1,0);
    }

    int dp(vector<int>& boxes,int l,int r,int k)
    {
        if(l>r)return 0;
        // 记忆化搜索
        if(f[l][r][k]!=0)return f[l][r][k];
        //k说明b[r]后面有K个和b[r]相同的值 即能连续删除 k + 1个b[r]
        while (r > l && boxes[r] == boxes[r - 1]) {
            r--;
            k++;
        }
        // 1 直接把包括boxes[r]在内的相邻相同的k全部移除,如果是样例中f[4,4,0] 则相当于dp(4,4-1,0)+(0+1)*(0+1)
        f[l][r][k] = dp(boxes,l,r-1,0)+(k+1)*(k+1);
        // 2 在[l, r -1]区间找到和b[r]相等的，合并起来一起删除 
        for(int i=l;i<r;i++)
        {
            if(boxes[i]==boxes[r])
            {
                f[l][r][k]=max(f[l][r][k],dp(boxes,l,i,k+1)+dp(boxes,i+1,r-1,0));
            }
        }
        return f[l][r][k];
    }
};

664 奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印同一个字符序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。

给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。

示例

输入: "aaabbb"
输出: 2
解释: 首先打印 "aaa" 然后打印 "bbb"。

数据范围

输入字符串的长度不会超过 100。

思路

状态表示
$f[i][j]$：区间$[i,j]$需要打印的次数
状态转移
首先对于任意字符串我们从后往前遍历,首先假设$s[i]$和$s[i+1:]$没有一个相同字符串:

$f[i][j]=f[i+1][j]+1$

对于$s[i:j]$ 如果其中有$s[k]==s[i]$,则说明$s[i:k]$可以先同时都打印$s[i]$,之后$s[k]$就不用管了,然后再看$s[i:k-1]$需要打印多少次和$s[k+1,j]$需要打印多少次

$f[i][j] = min(f[i+1][j]+1,f[i][k-1]+f[k+1][j] \quad for \quad s[k]==s[i] ,k\in(i,j) )$

初始化
区间是从小到到大来动态规划，所以只需要初始化区间长度为1的就行，一个字母最少也要打印一次，
$f[i][i]=1$

class Solution {
public:
    int strangePrinter(string s) {
        const int N = 110;
        int f[N][N];
        memset(f,0,sizeof f);
        int n = s.size();
        if(n==0)return 0;
        for(int i=0;i<n;i++) f[i][i]=1;
        for(int i=n-2;i>=0;i--)
        {
            for(int j=i+1;j<n;j++)
            {
                f[i][j] = f[i+1][j]+1;
                for(int k=i+1;k<=j;k++)
                {
                    if(s[i]==s[k])
                    {
                        f[i][j] = min(f[i][j],f[i][k-1]+f[k+1][j]);
                    }
                }
            }
        }
        return f[0][n-1];
    }
};

leetcode 1000 合并石头的最低成本

思路

状态表示

$dp[i][j][k]$ 表示合并区间 $[i, j]$ 成 $k$ 堆的最小花费。
状态转移
1. 基础转移
  
  由于我们一次只能合并大K 堆，所以有一个基础的转移方程：
  
  dp[i][j][1] = dp[i][j][K] + sum(i, j)
2. 拆分转移
  
  遍历$[i,j]中的m$,分为两部分$[i,m],[m+1,j]$,第一部分为$1$堆,第二部分为$k-1$堆
  
  $dp[i][j][k] = min(dp[i][m][1] + dp[m+1][j][k-1]) i \leq m \lt j$

class Solution {
public:
    int mergeStones(vector<int>& stones, int K) {
        int n = stones.size();
        if((n-1)%(K-1))return -1;
        const int N=35;
        int f[N][N][N],s[N];
        memset(f,0x3f,sizeof f);
        for(int i=1;i<=n;i++)s[i] = stones[i-1]+s[i-1];
        
        for(int i=0;i<=n;i++)f[i][i][1]=0;

        for(int i=n;i>=1;i--)
        {
            for(int j=i+1;j<=n;j++)
            {
                for(int k=2;k<=K;k++)
                {
                    for(int m=i;m<j;m++)
                    {
                        f[i][j][k] = min(f[i][j][k],f[i][m][1]+f[m+1][j][k-1]);
                    }
                }
                f[i][j][1] = f[i][j][K]+s[j]-s[i-1];
            }
        }
        return f[1][n][1];
    }
};

leetcode 1039 多边形三角剖分的最少个数

给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

示例

输入：[1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。

数据范围

3 <= A.length <= 50
1 <= A[i] <= 100

思路

状态表示

$f[l][r]$表示区间 $[l,r]$ 的元素 $a_l, a_{l + 1}, a_{l + 2} \cdots a_r$
三角剖分的最少个数。
状态转移

遍历$[l+1,r-1]$中间的$m$,则
假设已经计算好了$f[l,m]$及$f[m,r]$,则两边加上中间$l,m,r$三点构成的三角形即为一种$f[l,r] = min(A[i]A[m]A[r]+f[l][m]+f[m][r]) for m in [i+1,j-1]$

class Solution {
public:
    int minScoreTriangulation(vector<int>& A) {
        int n = A.size();
        const int N=55;
        int f[N][N];
        memset(f,0,sizeof f);
        for(int i=n-3;i>=0;i--)
        {
            for(int j=i+2;j<n;j++)
            {
                for(int m=i+1;m<j;m++)
                {
                    if(f[i][j])
                    {
                        f[i][j] = min(f[i][j],A[i]*A[m]*A[j]+f[i][m]+f[m][j]);
                    }
                    else
                    {
                        f[i][j] = A[i]*A[m]*A[j]+f[i][m]+f[m][j];
                    }
                }
            }
        }
        return f[0][n-1];
    }
};

博弈区间dp

leetcode 486 预测赢家

给定一个表示分数的非负整数数组。玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例

输入：[1, 5, 2]
输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。

数据范围

1 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于 10000000 。
如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        const int N=25;
        int f[N][N];
        memset(f,0,sizeof f);
        int n=nums.size();
        for(int i=0;i<n;i++)f[i][i]=nums[i];
        for(int i=n-2;i>=0;i--)
        {
            for(int j=i+1;j<n;j++)
            {
                f[i][j] = max(nums[i]-f[i+1][j],nums[j]-f[i][j-1]);
            }
        }
        return f[0][n-1]>=0;
    }
};

leetcode 1690 石子游戏Ⅶ

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始。

有 n 块石子排成一排。每个玩家的回合中，可以从行中移除最左边的石头或最右边的石头，并获得与该行中剩余石头值之和相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力减小得分的差值。爱丽丝的目标是最大限度地扩大得分的差值。

给你一个整数数组stones ，其中 stones[i] 表示从左边开始的第 i 个石头的值，如果爱丽丝和鲍勃都发挥出最佳水平，请返回他们得分的差值。

示例：

输入：stones = [5,3,1,4,2]
输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。

输入：stones = [7,90,5,1,100,10,10,2]
输出：122

数据范围：

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

思路

思路同486,都是最大化自己当前获得-对手已经获得,只不过算分是用区间和算的

状态表示

$f[i][j]$：先手在$[i:j]$时进行操作的最大收益
状态转移

构建前缀和数组$s$
则当前有两种抉择
- 取出$stones[i]$,获得$s[j]-s[i]$,对手获得$f[i+1][j]$
- 取出$stones[j]$,获得$s[j-1]-s[i-1]$,对手获得$f[i][j-1]$
  
  则有
  
  $f[i][j] = max(s[j]-s[i]-f[i+1][j],s[j-1]-s[i-1]-f[i][j-1])$
初始化

$f[i][i]=0$:只剩下一个时,取出后剩下的石子之和=0

答案

$f[1][n]$

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<vector<int>> f(n+1,vector<int>(n+1,0));
        vector<int> s(n+1,0);
        s[0]=stones[0];
        for(int i=1;i<=n;i++)s[i] = s[i-1]+stones[i-1];
        
        for(int i=n-1;i>=1;i--)
        {
            for(int j=i+1;j<=n;j++)
            {
                f[i][j]=max(-f[i+1][j]+s[j]-s[i],-f[i][j-1]+s[j-1]-s[i-1]);
            }
        }
        return f[1][n];
    }
};

Leopold

https://leopoldacc.github.io/Blogs/Blogs/2020/12/25/%E5%8C%BA%E9%97%B4dp/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Leopold !

区间型动态规划

模板总结

2021-04-21 数据结构与算法

模板

arxiv 2020 NAS-adversarial attacks

2020-12-24 计算机视觉

NAS Adversarial Attacks

区间DP

区间dp

回文系列

leetcode 5最长回文子串

示例：

思路

leetcode 516 最长回文子序列

示例:

数据范围：

思路

leetcode 647回文子串

示例：

数据范围

思路

leetcode 730 统计不同回文子序列

示例：

数据范围：

思路

leetcode 1147 段式回文

段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符而不是 单个字母。

示例：

数据范围：

思路

leetcode 1312 让字符串成为回文串的最少插入次数

示例

提示：

思路

其他区间dp

leetcode 312 戳气球

数据范围

示例

思路

leetcode 471 编码最短长度的字符串

示例

数据范围

思路

leetcode 546 移除盒子

示例

数据范围

思路

664 奇怪的打印机

示例

数据范围

思路

leetcode 1000 合并石头的最低成本

思路

leetcode 1039 多边形三角剖分的最少个数

示例

数据范围

思路

博弈区间dp

leetcode 486 预测赢家

示例

数据范围

leetcode 1690 石子游戏Ⅶ

示例：

数据范围：

思路

你的赏识是我前进的动力

段式回文其实与一般回文类似，只不过是最小的单位是一段字符而不是单个字母。