動的計画法(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)になるが、text1のi番目までとtext2のj番目までの共通部分列の長さをDP[i-1][j-1]に記録しておくと、
ヒントにあるように、それぞれの文字列に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()];
}
};
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)で、タイムアウトしてしまう。
class 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_nは max(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が条件を満たすなら、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も同様に解ける。
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()];
}
};
個数制限なしナップザック問題
通常のナップザック問題は、重さw_iで価値v_iのナップザックがN個あり、重さの和がWを超えないように選んだときの価値の和の最大値を求める問題。値は全て正の整数。
単純に総当たりするとO(2^N)となりNが大きいとうまくいかない。
DPを用いてi番目以降のナップザックから重さがWを超えないように選んだ時の価値の和の最大値を返す関数f(i, W)の値をDP[i][W]に記録しておくと、この関数は次の漸化式の値を返すだけで引数のパターンはN*WしかないのでO(NW)で実行できる。
int f(int i, W) {
return max(DP[i+1][W], DP[i+1][W-w[i]] + v[i]);
}
なお、Wがとても大きいとタイムアウトする可能性があるが、その場合i番目以降のナップザックから価値の和vとなるように選んだ時の重さの最小値 f(i, v) を記録し、DP[i][v] <= W となる最大のvを返すようにすることでオーダーをWに依存しない O(N Σv) にすることができる。
個数制限なしナップザック問題は同じナップザックを複数個選ぶことができるようにしたもの。
次のようにループで個数kを探索すると、w[i]=1, W=0のときにW回ループするのでO(NW^2)となってしまう。
int f(int i, W) {
int m = DP[i + 1][W];
int k = 0;
while(true) {
k++;
if (W - k * w[i] < 0) {
break;
}
m = max(m, DP[i+1][W - k * w[i]] + k * v[i]);
}
return m;
}
f(i, W)でk(>=1)個選んだときに価値が最大となる場合、その値は f(i, W - k * w[i]) + k * v[i] と等しくなる。
そのkを探すために結局 f(i, W - 1 * w[i]), f(i, W - 2 * w[i]) … を見ていくことになりそうだが、
f(i, W - 1 * w[i]) で既に f(i, W - 2 * w[i]), f(i, W - 3 * w[i]), … を見ているので、1個分Wが小さいときの値だけ見ればkの探索は不要であることが分かる。
したがって、f(i, W) = max(f(i+1, W), f(i, W - w[i]) + v[i]) (if W - w[i] >= 0) となり O(NW) にすることができる。