阿祁的部落格

TOI 2021/10 潛力組(二)-收納盒 Java解題心得( 題目 )

解題概念:DP

解題方法:這題在填入括弧時需恆有左括弧大於右括弧的條件，我們可以定義dp[i][j]=k，代表只討論前面i格，使得左括弧數量比右括弧多j個的方法數為k，而轉移三種情況為:

1.[  dp[i][j]=dp[i-1][j-1]

2.]  dp[i][j]=dp[i-1][j+1]

3.? dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1]

(另外注意j的範圍)

最後答案為dp[字串長度][0] (就是最後左右要一樣)

下方DP使用到了滾動優化(空間複雜度由n^2降為n)

Java參考程式碼(有更好意見可留言於下方，謝謝!)

//Author:欉恩祁

import java.io.*;

import java.util.*;

public class zjg545 {

   public static long[][] dp=new long[2][1005];
 
   public static void main(String[] args) throws Exception {
 
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 
        String[] in=br.readLine().split(" ");
 
        final int n=Integer.parseInt(in[0]);
 
        int r,id=0;
 
        final long mod=1000000007;
 
        dp[0][0]=1;//default
 
        for(int i=0;i<n;i++) {
 
            r=br.read();
 
            if(r=='[') {
 
                dp[id^1][0]=0;
 
                for(int j=1;j<1005;j++) {
 
                    dp[id^1][j]=dp[id][j-1];//放[
 
                }
 
            }
 
            else if(r==']') {
 
                for(int j=1;j<1005;j++) {
 
                    dp[id^1][j-1]=dp[id][j];//放 ]
 
                }
 
            }
 
            else {
 
                Arrays.fill(dp[id^1],0);//設為0
 
                for(int j=1;j<1005;j++) {
 
                    dp[id^1][j]+=dp[id][j-1];//放[
 
                    dp[id^1][j-1]+=dp[id][j];//放 ]
 
                }
 
                for(int j=0;j<1005;j++) {
 
                    dp[id^1][j]%=mod;//mod值
 
                }
 
            }
 
            id^=1;
 
        }
 
        System.out.println(dp[id][0]);
 
   }

}