動的計画法(DP)で計算結果を再利用して計算量を減らす

(2019-12-30)

動的計画法(DP, Dynamic Programming)は記録した計算結果を、帰納的に求められるより大きな計算で利用するアルゴリズムの総称。 例えば、フィボナッチ数列の項f(x)を求めるのに、f(x-1)f(x-2)の結果を記録しておけばそれらを足すだけで済む。

いくつか問題を解いてみる。

Longest Common Subsequence

最長共通部分列問題。

Given two strings text1 and text2, return the length of their longest common subsequence.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

単純に毎回一から探索するとO(n^3)になるが、 ヒントにあるように、それぞれの文字列に1文字足したときに それが同じ文字ならその分伸ばした DP[i - 1][j - 1] + 1 となり 違う文字ならそのまま max(DP[i - 1][j], DP[i][j - 1]) となる ことに気付けると毎回探索しなくてよくなりO(n^2)にできる。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> DP(text1.length()+1); // [i][j] = length
        vector<int> tmp(text2.length()+1, 0);
        DP[0] = tmp;
        for(int i = 0; i < text1.length(); i++) {
            vector<int> tmp(text2.length()+1, 0);
            DP[i+1] = tmp;
            for(int j = 0; j < text2.length(); j++) {
                if (text1[i] == text2[j]) {
                    DP[i+1][j+1] = DP[i][j] + 1;
                } else {
                    DP[i+1][j+1] = max(DP[i][j+1], DP[i+1][j]);
                }
            }
        }
        return DP[text1.length()][text2.length()];
    }
};

Longest Palindromic Substring - LeetCode

文字列に含まれる最長の回文を返す問題。

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

最初に書いたコードはこれ。オーダーは部分文字列を網羅するのにO(n^2)*回文かチェックするのにO(n)=O(n^3)で、タイムアウトしてしまう。

cclass Solution {
    bool isPalindromic(string s) {
        for (int i = 0; i < (s.length() / 2) + 1; i++) {
            if (s[i] != s[s.length() - 1 - i]) {
                return false;
            }
        }
        return true;
    }
public:
    string longestPalindrome(string s) {
        string ret = "";
        for (int i = 0; i < s.length(); i++) {
            if (ret.length() >= s.length() - i) {
                break;
            }
            for (int j = s.length(); j >= i+1; j--) {
                if (ret.length() >= j - i) {
                    break;
                }
                string substr = s.substr(i, j - i);
                if (isPalindromic(substr)) {
                    ret = substr;
                    break;
                }
            }
        }
        return ret;
    }
};

今回の問題ではある文字列Sが回文なら、その両端に同じ文字cが付いた文字列cScも回文であることを利用し、 中央の文字を決めて、回文である限り範囲を両端に伸ばしていくことで、回文判定が両端の文字の一致だけのO(1)でできるようになった。 これにより全体のオーダーがO(n^2)に改善され、タイムアウトしなくなった。

class Solution {
    bool isPalindromic(string s) {
        return s[0] == s[s.length() - 1];
    }
public:
    string longestPalindrome(string s) {
        string ret = "";
        for (int i = 0; i < s.length(); i++) {
            if (ret.length() >= min(i*2+2, int(s.length()-i)*2+2)) {
                break;
            }
            for (int j = 1; j <= 2; j++) {
                if(i+j > s.length()) {
                    break;
                }
                string substr = s.substr(i, j);
                if (!isPalindromic(substr)) {
                    break;
                }
                for (int k = 0; k <= i; k++) {
                    if (i+j+k > s.length()) {
                        break;
                    }
                    substr = s.substr(i-k, j+k*2);
                    if (!isPalindromic(substr)) {
                        break;
                    }
                    if (ret.length() < substr.length()) {
                        ret = substr;
                    }
                }
            }
        }
        return ret;
    }
};

Maximum Sum Circular Subarray - LeetCode

最大部分配列問題の配列が循環する版。

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

最大部分配列問題をO(n)で解く方法としてKadane’s algorithmというのがあって、 配列Aのn番目の要素A[n]を末尾とする部分配列のうち最大のものの和S_nmax(S_{n-1} + A[n], A[n]) となるので、これを配列の始めから順に計算することでSが最大となる最大部分配列を探すことができる。

この問題では配列が循環しているので [10, -5, 10] のような場合、末尾と先頭の10を部分配列として扱わなければいけない。 そこで、始まりのindexをずらしてローテーションしたのが次の実装。ただこれだとタイムアウトしてしまう。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int ret = INT_MIN;
        for (int i = 0; i < A.size(); i++) {
            int S = 0;
            for(int j = 0; j < A.size(); j++) {
                S = max(S+A[(j+i) % A.size()], A[(j+i) % A.size()]);
                ret = max(ret, S);
            }
        }
        return ret;
    }
};

両端またぎのケースは別に扱い、最小の部分を探して総和から引くようにしたのが次の実装。これでO(n)になり通るようになった。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        // case 1. [... --answer-- ...]
        long maxsub = A[0];
        long sum = A[0];
        long S = A[0];
        for (int i = 1; i < A.size(); i++) {
            S = max(S+A[i], long(A[i]));
            maxsub = max(maxsub, S);
            sum += A[i];
        }
        
        // case 2. [wer-- ...... --ans]
        long minsub = A[0];
        S = A[0];
        bool isSubarray = false;
        for (int i = 1; i < A.size(); i++) {
            if (S+A[i] >= A[i]){
                isSubarray = true;
                S = A[i];
            } else {
                S += A[i];
            }
            minsub = min(minsub, S);
        }
        
        if (isSubarray) {
            return max(maxsub, sum - minsub);
        } else {
            return maxsub;
        }
    }
};

Ugly Number II - LeetCode

2, 3, 5のみで素因数分解できるn番目の正数を返す問題。

Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 

Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Nが条件を満たすなら、N2, N3, N*5が条件を満たすので、これらの値を重複しないように記録していく。

class Solution {
public:
    int nthUglyNumber(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        
        vector<int> U;
        U.push_back(1);
        int idx2 = 0, idx3 = 0, idx5 = 0;
        for (int i = 2; i <= n; i++) {
            int next = min(U[idx2] * 2, min(U[idx3] * 3, U[idx5] * 5));
            U.push_back(next);
            while (U[idx2] * 2 <= next) idx2++;
            while (U[idx3] * 3 <= next) idx3++;
            while (U[idx5] * 5 <= next) idx5++;
        }
        return U[U.size() - 1];
    }
};

対象の素数が引数で渡されるSuper Ugly Number - LeetCodeも同様に解ける。

Interleaving String - LeetCode

2つの文字列を順番を変えずに組み合わせてある文字列が作れるかを判定する問題。

Given s1, s2, and s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

基本的な戦略としてはs1かs2の先頭一文字を取り出すのを繰り返しs3の完成を目指すというものだが、 次のような再帰で解くと、2つの文字列が長く共通文字が多い場合にタイムアウトしてしまった。 一見O(n^2)に見えるが、どちらから取っても良い場合に両方の場合を探索してしまうので、最悪の場合はO(2^n)になってしまう。

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.size() == 0) {
            if (s1.size() == 0 && s2.size() == 0) {
                return true;
            } else {
                return false;
            }
        }
        bool b = false;
        if (s1.size() > 0 && s3[0] == s1[0]) {
            b = b || isInterleave(s1.substr(1), s2, s3.substr(1));
        }
        if (s2.size() > 0 && s3[0] == s2[0]) {
            b = b || isInterleave(s1, s2.substr(1), s3.substr(1));
        }
        return b;
    }
};

ということで次のようなテーブルで重複しないように探索し O(n^2) になるようにした。

テーブル

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.size() != s1.size() + s2.size()) {
            return false;
        }
        vector<vector<bool>> table;
        for (int i = 0; i < s1.size()+1; i++) {
            table.push_back({});
            for (int j = 0; j < s2.size()+1; j++) {
                if (i == 0 && j == 0) {
                    table[i].push_back(true);
                } else if (i == 0) {
                    table[i].push_back(table[i][j - 1] && s2[j-1] == s3[i + j - 1]);
                } else if (j == 0) {
                    table[i].push_back(table[i - 1][j] && s1[i-1] == s3[i + j - 1]);
                } else {
                    table[i].push_back(
                        (table[i - 1][j] && s1[i-1] == s3[i + j - 1]) ||
                        (table[i][j - 1] && s2[j-1] == s3[i + j - 1]));
                }
            }
        }
        return table[s1.size()][s2.size()];
    }
};