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

(2019-12-30)

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

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

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;
    }
};

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が条件を満たすなら、N*2, N*3, 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も同様に解ける。