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

c++algorithm

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

## 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.
``````

``````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:
Output: "bab"
Note: "aba" is also a valid answer.
``````

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

``````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.
``````

この問題では配列が循環しているので `[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];
}
};
``````

## 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
``````

``````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()];
}
};
``````

## 個数制限なしナップザック問題

``````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)` にすることができる。

``````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)` にすることができる。

## 参考

プログラミングコンテストチャレンジブック [第2版]