专栏首页Michael阿明学习之路LeetCode 1246. 删除回文子数组(区间DP)

LeetCode 1246. 删除回文子数组(区间DP)

1. 题目

给你一个整数数组 arr,每一次操作你都可以选择并删除它的一个 回文 子数组 arr[i], arr[i+1], ..., arr[j]( i <= j)

注意,每当你删除掉一个子数组,右侧元素都会自行向前移动填补空位。

请你计算并返回从数组中删除所有数字所需的最少操作次数。

示例 1:
输入:arr = [1,2]
输出:2

示例 2:
输入:arr = [1,3,4,1,5]
输出:3
解释:先删除 [4],然后删除 [1,3,1],最后再删除 [5]。
 
提示:
1 <= arr.length <= 100
1 <= arr[i] <= 20

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/palindrome-removal 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • dp[i][j] 表示区间 [i,j] 的最少移除次数
  • 如果已知 dp[i][j],推导dp[i-1][j+1]
  • 如果两侧相等 arr[i-1] == arr[j+1]dp[i-1][j+1] = min(dp[i-1][j+1], dp[i][j])
  • 对区间而言,把区间分成任意的两份,求和取最小 对所有可能的 k,dp[i-1][j+1] = min(dp[i-1][j+1], dp[i-1][k]+dp[k+1][j+1])
class Solution {
public:
    int minimumMoves(vector<int>& arr) {
        int n = arr.size(), i, j,k, len;
        vector<vector<int>> dp(n, vector<int>(n,INT_MAX));
        for(i = 0; i < n; ++i)
        {
        	dp[i][i] = 1;//初始化
        	if(i < n-1 && arr[i]==arr[i+1])
        		dp[i][i+1] = 1;
        	else if(i < n-1 && arr[i]!=arr[i+1])
        		dp[i][i+1] = 2;
        }
        for(len = 0; len < n; ++len)
        {	//按长度遍历
        	for(i = 0; i < n; ++i)
        	{
        		j = i+len;//右端点
        		if(j >= n || dp[i][j]==INT_MAX) continue;
        		if(i-1 >=0 && j+1 < n)
        		{
                    for(k = i-1; k <= j; ++k)
                        dp[i-1][j+1] = min(dp[i-1][j+1], dp[i-1][k]+dp[k+1][j+1]);
        			if(arr[i-1] == arr[j+1])
        				dp[i-1][j+1] = min(dp[i-1][j+1], dp[i][j]);
        		}      
        	}
        }
        return dp[0][n-1];
    }
};

440 ms 12.9 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1289. 下降路径最小和 II(DP)

    给你一个整数方阵 arr ,定义「非零偏移下降路径」为:从 arr 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。

    Michael阿明
  • LeetCode 241. 为运算表达式设计优先级(动态规划)

    给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。 你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 *...

    Michael阿明
  • 程序员面试金典 - 面试题 01.05. 一次编辑(编辑距离,DP)

    字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。

    Michael阿明
  • 周末小圆桌 |第1期

    从本周开始,我开设了「周末小圆桌」这个栏目。内容是挑选这一周来大家相互讨论或向我提问的最有代表性的7个问题,整理出来分享给大家。只之所以取名「小圆桌」,是希望能...

    Shawn.W
  • 组内刷题之LeetCode第188周赛解题思路

    题目:给你一个目标数组 target 和一个整数 n。每次迭代,需要从 list = {1,2,3..., n} 中依序读取一个数字。

    公众号guangcity
  • Pillpack:颠覆医疗的线上药房

    大数据文摘
  • 【iOS开发】iOS路由引入及遇到的问题

    路由是指根据url分配到对应的处理程序,在移动端就可以理解为,根据给定的url跳转到指定页面的功能模块。

    吴老师
  • ASM 关键接口 MethodVisitor

    Label label = new Label() 这个语句中,label的作用是为了条件跳转,其实也可以理解成字节码指令的参数。 所以label必须对应一...

    JavaEdge
  • Go进阶03:怎么使用viper管理配置

    viper 是以个完善的go语言配置包.开发它的目的是来处理各种格式的配置文件信息.

    mojocn
  • C#并发编程之初识并行编程

    之前微信公众号里有一位叫sara的朋友建议我写一下Parallel的相关内容,因为手中商城的重构工作量较大,一时之间无法抽出时间。近日,这套系统已有阶段性成果,...

    Edison.Ma

扫码关注云+社区

领取腾讯云代金券