풀이

DP배열을 생성해, Bottom Up방식으로 풀이.

dp[0]=1이 왜 1인가에 대해 고민을 좀 많이 했던 문제였다.

문자열의 길이가 0인게 없지않나?? 라는 생각을 많이했다.

1. 문자열의 길이가 0인 경우가 ""의 경우가 존재할 수도 있겠구나라는 생각

2. dp[0]을 1로 설정해주지 않으면 문제 풀이자체가 되지않겠구나. dp[i]=0일테니까.

고민을해서 위와 같은 결론을 내렸다.

위의 그림은, 해당 문제의 Solution 탭의 그림의 일부인데.

문제에서 말하는 좋은 문자열이 되기 위해서는

1. 마지막에 해당 숫자만큼 붙였을때 알맞은 길이의 숫자가 되는것

2. 그러기 위해서는 i가 zero, one보다 크거나 같을때 : 해당 dp[i]가 ++될 것이다.

까지 생각을 할 수 있었다.

이게 무슨말인고? 하니

위의 그림에서 자세하게 idx = 5까지가는 과정을 살펴보자.

모든 dp[idx]배열의 값에, 들어갈 수 있는 경우의 수는

dp[idx-zero]나, dp[idx-one] 두 경우에서 만족하는 경우의 배열들을 추가해준 값이 해당 dp[idx]에 들어갈 수 있는 총 문자열의 개수가 될 수밖에 없다.

class Solution {
    public int countGoodStrings(int low, int high, int zero, int one) {
    	int answer = 0;    	    	
    	int[] dp = new int[high+1];
    	dp[0] = 1;

    	for(int i=1; i<=high; ++i) {
    		if(i>=zero) dp[i] += dp[i-zero];
    		if(i>=one) dp[i] += dp[i-one];
    		
    		dp[i] %= 1_000_000_007;
    	}
    	
    	for(int i=low; i<=high; i++) {
    		answer += dp[i];
    		answer %= 1_000_000_007;
    	}
    	
        return answer;
    }
}

O(n) (n=high)의 시간복잡도를 가지는 코드가 완성됐다.

풀이

DP배열의 idx의 값은 해당 idx까지 서로 탐색을했을때, 겹치지 않는 최대 경우의 수를 나타낸다.

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        int[] dp = new int[m+1];
        for (int i=1; i<=n; i++) {
        	int prev = 0;
            for (int j=1; j<=m; j++) {
                int curr = dp[j];
                if (nums1[i-1] == nums2[j-1]) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j-1], curr);
                }
                prev = curr;
            }
        }
        return dp[m];
    }
}