问题描述
给定一个字符串str,允许删除相同的连续字符。你的任务是找到完全删除字符串所需的最小操作数。
例如:给定字符串 str = “abcddcba”
输出结果为: 4
删除 dd, 字符串变为: “abccba”
删除 cc, 字符串变为: “abba”
删除 bb, 字符串变为: “aa”
删除 aa, 字符串变为: null
所以,删除字符串的最少删除次数为:4 次
例如:给定字符串 str = “abc”
输出结果为:3
算法分析
采用动态规划算法。
设定一个dp数组,令 dp[m][n] 表示删除字符串 str[ m,m+1,m+2,...n ] 的最少删除次数,即为我们需要获得的答案。
我们会有两种情况:
- 子字符串的第一个字母与其余字母分开删除,然后dp[m][n]=1+dp[m+1][n]。
- 子字符串的第一个字母与其他字母一起删除(两个字母必须相等),然后dp[m][n]=dp[m+1][n-1]+dp[i][n],前提是m≤i≤n和s[i]=s[m]。
算法设计
package com.bean.algorithm.dp;public class MinimumStepsofDeleteCharacters {static int findMinimumDeletion(int m, int n, int dp[][], String s) {if (m > n) {return 0;}