💎蓝桥杯系列文章

2023第十四届蓝桥杯模拟赛第二期个人题解（Java实现）
2023第十四届蓝桥杯模拟赛第三期个人题解（Java实现）
蓝桥杯备赛之动态规划篇——背包问题

蓝桥杯真题——单词分析（Java实现）

💎动态规划篇——涂色问题

• 💎蓝桥杯系列文章
• 💎前言
• 💎温故而知新
• 💎区间DP
• • 🎯涂色
  • • 🌞问题分析
    • 💡 Java代码
• 💎总结

💎前言

😘😘哈喽，大家好！这里是蓝桥杯系列文章的动态规划章节🔥🔥，今天要讲解的是区间动态规划的经典问题——涂色问题🍄

🙊🙊如果我写的内容有误，欢迎大家在评论区指正👏希望这篇文章对你有帮助❤❤同时欢迎关注我呦👇👇

💎温故而知新

🎬🎬首先再通过思维导图来回顾一下闫氏DP分析法：

🍄🍄如果新来的小伙伴还不知道是啥，可以去我看我上一篇文章，有详细介绍哦👇👇
🔥🔥蓝桥杯备赛之动态规划篇——背包问题🔥🔥

💎区间DP

🎯涂色

题目地址
　　 蓝桥云课题库——涂色
问题描述
　　假设你有一条长度为 5 的木版，初始时没有涂过任何颜色。你希望把它的 5 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 5 的字符串表示这个目标：RGBGR。
　　每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成 RRRRR，第二次涂成 RGGGR，第三次涂成 RGBGR，达到目标。
　　用尽量少的涂色次数达到目标。
输入格式
　　输入仅一行，包含一个长度为 n 的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
　　其中，1 ≤ n ≤ 50。
输出格式
　　输出仅一行，包含一个数，即最少的涂色次数。
样例输入
　　AAAAA
样例输出
　　1
评测用例规模与约定
　　最大运行时间：1s
　　最大运行内存: 128M

🌞问题分析

📢📢 这道题用闫氏DP分析法该如何思考呢？
🐾🐾 状态表示：
  涂色问题可以看做一个二维的问题，用f(i,j)表示
  集合定义： 将区间 [ i , j ] 上染成涂色目标的所有涂色方案的集合。
  集合属性： 所有涂色方案中的最少涂色次数。
🐾🐾 状态计算：
  集合划分： 寻找最后一个不同点，即 i 和 j 颜色是否相同：区间$[i,j]$左右端点颜色相同、区间$[i,j]$左右端点颜色不同。
  对于所有区间$[i,j]$左右端点颜色相同的涂色方案:
   m i n { f ( i , j − 1 ) , f ( i + 1 , j ) } min\{f(i ,j-1),f(i+1,j)\} min{f(i,j−1),f(i+1,j)}
  对于所有区间$[i,j]$左右端点颜色不同的方案：再将区间$[i,j]$分为$[i,k]$和$[k+1,j]$两段，即
  $f(i,k)+f(k+1,j)$
最大价值只需取两种方案中的最小值:
f ( i , j ) = m i n { f ( i , j − 1 ) , f ( i + 1 , j ) , f ( i , k ) + f ( k + 1 , j ) } f(i,j) = min\{f(i ,j-1),f(i+1,j) ,f(i,k)+f(k+1,j)\} f(i,j)=min{f(i,j−1),f(i+1,j),f(i,k)+f(k+1,j)}

最后f(1,N)即区间[1,N]上染成涂色目标的最少涂色次数。

💡 Java代码

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String color=sc.next();//涂色目标字符串
		int n=color.length();
		int[][] dp=new int[n+1][n+1]; //dp[i][j]代表子串区间[i,j]的所有涂色方案中的最少涂色次数
		for(int len=1;len<=n;len++) {	//区间dp，遍历所有区间长度，从1开始到n
			for(int i=1;i+len-1<=n;i++) {	//遍历每个子区间，i是子区间左端点，j是子区间右端点
				int j=i+len-1;
				if(len==1) {	//区间长度是1时，只有1种涂色方案，最少涂色次数是1
					dp[i][j]=1;
					continue;
				}
				dp[i][j]=100000000;	//初始化为一个很大的值，便于后续更新
				String subStr=color.substring(i-1, j);	//截取字符串子区间
				if(subStr.charAt(0)==subStr.charAt(len-1))//如果子区间左端点和右端点是同个颜色
					dp[i][j]=Math.min(dp[i][j-1],dp[i+1][j]);//最少涂色次数=min{除去右端点时的涂色次数，除去左端点时的涂色次数}
				else {//如果子区间左端点和右端点不是同个颜色
					for(int k=i;k<j;k++) 	//将子区间划分为[i,k]和[k+1,j]两段
						dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k+1][j]);//找出所有划分中，区间[i,k]和[k+1,j]着色次数之和的最小值
				}
			}
		}
		System.out.println(dp[1][n]);//字符串区间[1,n]的最少涂色次数
	}

}

💎总结

💥💥区间DP的写法比较固定，有三层for循环：
第一层for循环：遍历区间长度
第二层for循环：遍历子区间左端点
第三层for循环：遍历子区间的每个元素

🔥🔥如果你觉得这篇文章对你有帮助，欢迎点赞评论收藏，或者关注我呦！！！爱你们💕💞