最长湍流数组
二指输入的最小距离
二至输入的最小距离
dp[i][j][k]：对于第i个字符左手指和右手指的位置
dp[i][cur][k]
dp[i][j][cur] 从上一个字符 i-1所有的左右手指位置状态转移
class Solution {
public int minimumDistance(String word) {
int n=word.length();
int[][][] dp=new int[n][26][26];
for(int i=0;i<n;i++){
for(int j=0;j<26;j++){
Arrays.fill(dp[i][j],Integer.MAX_VALUE);
}
}
for(int i=0;i<26;i++){
dp[0][word.charAt(0)-'A'][i]=0;
dp[0][i][word.charAt(0)-'A']=0;
}
int res=Integer.MAX_VALUE;
for(int i=1;i<n;i++){
int cur=word.charAt(i)-'A';
int prev=word.charAt(i-1)-'A';
for(int j=0;j<26;j++){
for(int k=0;k<26;k++){
//对于上一次的所有情况
if(dp[i-1][j][k]!=Integer.MAX_VALUE){//初始时候必须从第一个word.charAt(0)-'A'转移过去
dp[i][cur][k]=Math.min(dp[i][cur][k],dp[i-1][j][k]+getDistance(j,cur));
dp[i][j][cur]=Math.min(dp[i][j][cur],dp[i-1][j][k]+getDistance(k,cur));
}
if(i==n-1){
res=Math.min(res,dp[i][cur][k]);
res=Math.min(res,dp[i][j][cur]);
}
}
}
}
return res;
}
public int getDistance(int start,int end){
int start_x=start/6;int start_y=start%6;
int end_x=end/6;int end_y=end%6;
return Math.abs(start_x-end_x)+Math.abs(start_y-end_y);
}
}
反转字符
翻转0-1字符串
将一个0-1字符串转为递增字符串的最小反转次数 对于字符串状态中间会发生变化的dp,可以通过增加一个维度进行状态转移
【对于决策型dp】比如买卖股票问题可以通过dp[i][k][0] dp[i][k][1]表示前i天，交易k次，第i天是否卖出 通过第三个维度0-1决策变量 0-1规划
dp[i][0]表示前i个字符，第i个字符最终为0时的反转为递增字符串的最少反转次数
dp[i][1]表示前i个字符，第i个字符最终为1时的反转为递增字符串的最少反转次数
class Solution {
public int minFlipsMonoIncr(String s) {
int n=s.length();
int[][] dp=new int[n][2];
if(s.charAt(0)=='0'){
dp[0][1]=1;
}
if(s.charAt(0)=='1'){
dp[0][0]=1;
}
for(int i=1;i<n;i++){
if(s.charAt(i)=='0'){
dp[i][0]=dp[i-1][0];
dp[i][1]=Math.min(dp[i-1][0],dp[i-1][1])+1;
}
else{
dp[i][0]=dp[i-1][0]+1;
dp[i][1]=Math.min(dp[i-1][0],dp[i-1][1]);
}
}
// for(int i=0;i<n;i++){
// System.out.println(dp[i][0]+"==="+dp[i][1]);
// }
return Math.min(dp[n-1][0],dp[n-1][1]);
}
}
方式二:通过前缀和 枚举所有的0-1分界线
class Solution {
public int minFlipsMonoIncr(String s) {
//可以通过前缀和
int n=s.length();
int[] prefix=new int[n+1];
for(int i=0;i<n;i++){
prefix[i+1]=prefix[i]+(s.charAt(i)=='1'? 1:0);
}
int res=Integer.MAX_VALUE;
for(int i=0;i<=n;i++){
int ans=prefix[i]+n-i-(prefix[n]-prefix[i]);
res=Math.min(res,ans);
}
return res;
}
}
是字符串变平衡的最少删除次数
是字符串变平衡的最少删除次数
// 删除对应的字符等价于将对应的字符进行反转的最少次数
class Solution {
public int minimumDeletions(String s) {
int n=s.length();
int[] prefix=new int[n+1];
for(int i=0;i<n;i++){
prefix[i+1]=prefix[i]+(s.charAt(i)=='b'? 1:0);
}
int res=Integer.MAX_VALUE;
for(int i=0;i<=n;i++){
res=Math.min(res,prefix[i]+n-i-(prefix[n]-prefix[i]));
}
return res;
}
}
最长斐波那契数列
最长斐波那契数列
给定dp状态转移方式，dp[i]=dp[j]+dp[k];
dp[i][j]表示当以i，j结尾的斐波那契子序列 的子序列长度
判断是否存在k使得dp[i]=dp[j]+dp[k]，如果存在dp[i][j]=dp[j][k]+1 否则dp[i][j]=2
class Solution {
public int lenLongestFibSubseq(int[] arr) {
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<arr.length;i++){
map.put(arr[i],i);
}
int n=arr.length;
int[][] dp=new int[n][n];
int res=0;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
int k=map.containsKey(arr[i]-arr[j])&&map.get(arr[i]-arr[j])<j? map.get(arr[i]-arr[j]):-1;
if(k==-1){
dp[i][j]=2;
}else{
dp[i][j]=dp[j][k]+1;
}
res=Math.max(res,dp[i][j]);
}
}
return res>2? res:0;
}
}
选择建筑的方案数
选择建筑的方案数
通过暴力枚举所有方案进行统计 所有的方案只包括 010 101两种，所以对中心点进行枚举
class Solution {
public long numberOfWays(String s) {
//通过暴力枚举的方式
long res=0;
int cnt=0;
int n1=0;
int n=s.length();
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='1'){
n1++;
}
}
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='1'){
// 左边0个数为i-cnt
res+=(i-cnt)*(n-i-n1+cnt);
//因为对应的s[i]==1占掉一个1，所以右边1个数为n1-cnt-1 n-i-1-(n1-cnt-1)==n-i-n1-+cnt对应的0的个数
cnt++;
}else{
res+=(cnt)*(n1-cnt);
}
}
return res;
}
}
对于字符串长度为k的情况，通过dp
dp[i][k][0]:表示前i个建筑，选择k个建筑，最后一个选择的是0类型的建筑
dp[i][k][1]:表示前i个建筑，选择k个建筑，最后一个选择的是1类型的建筑
if(s.charAt(i)==‘0’){
dp[i][k][0]=dp[i-1][k][0]+dp[i-1][k-1][1];//可以选也可以不选
dp[i][k][1]=dp[i-1][k][1];//必须不选
}else{
dp[i][k][0]=dp[i-1][k][0];//必不选
dp[i][k][1]=dp[i-1][k][1]+dp[i-1][k-1][0];//可选可不选
}
class Solution {
public long numberOfWays(String s) {
int n=s.length();
int m=3;
long[][][] dp=new long[n][m+1][2];
for(int i=0;i<n;i++){
dp[i][0][0]=dp[i][0][1]=1;
}
for(int k=0;k<=m;k++){
if(s.charAt(0)=='0'){
dp[0][1][0]=1;
}else{
dp[0][1][1]=1;
}
}
for(int i=1;i<n;i++){
for(int k=1;k<=m;k++){
if(s.charAt(i)=='0'){
dp[i][k][0]=dp[i-1][k-1][1]+dp[i-1][k][0];
dp[i][k][1]=dp[i-1][k][1];
}else{
dp[i][k][0]=dp[i-1][k][0];
dp[i][k][1]=dp[i-1][k-1][0]+dp[i-1][k][1];
}
}
}
return dp[n-1][3][0]+dp[n-1][3][1];
}
}
