山西大同网站建设哪家好,网站内链优化的角度,专业网站定制价格便宜,合肥手机网站开发文章目录1. 题目2. 解题1. 题目
描述 有n个瓶子排成一列#xff0c;用arr表示。 你每次可以选择能够形成回文连续子串的瓶子拿走#xff0c;剩下的瓶子拼接在一起。 返回你能拿走所有的瓶子的最小次数。
n500
arr[i]1000示例
例1:
输入#xff1a;[1,3,4,1,5]
…
文章目录1. 题目2. 解题1. 题目
描述 有n个瓶子排成一列用arr表示。 你每次可以选择能够形成回文连续子串的瓶子拿走剩下的瓶子拼接在一起。 返回你能拿走所有的瓶子的最小次数。
n500
arr[i]1000示例
例1:
输入[1,3,4,1,5]
输出3
说明第一次先拿走[4]剩余[1,3,1,5]
第二次拿走[1,3,1]剩余[5]
第三次拿走[5]例2:
输入[1,2,3,5,3,1]
输出2来源https://tianchi.aliyun.com/oj/141754208384739500/160296091929219254
2. 解题
区间DPdp[i][j] 表示区间 [i, j] 需要拿的最少次数
class Solution {
public:/*** param arr: the array of bottles* return: the minimum number of times you can take all the bottles*/int takeAwayTheBottle(vectorint arr) {// Write your code here.int n arr.size();if(n 0)return 0;vectorvectorint dp(n, vectorint(n, INT_MAX));for(int i 0; i n; i)dp[i][i] 1;//初始化长度为1的区间for(int i 1; i n; i)if(arr[i-1] arr[i])//初始化长度为2的区间dp[i-1][i] 1;elsedp[i-1][i] 2;for(int len 2; len n; len){ // 区间长度for(int i 0; ilen n; i){int j ilen;if(arr[i] arr[j])//左右端点相等dp[i][j] dp[i1][j-1];for(int k i; k j; k) //左右端点 不相等区间切开dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j]);}}return dp[0][n-1];}
};603ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
