用类似这一recurrence的题非常多，在这汇总一下
INPUT: i, j, sum
for all i <= k <= j take out substring(i,k) from sum try d[k+1][j] = solve(substring(k+1,j), sum - substring(i,k)); end for d[i][j] = min (1+d[k+1][j]) k=i...j
边缘情况注意一下，如果d[i][j]整体已经等于sum，直接返回，不用1+res
#define INF 999999999
int memo[12][12][102];
void checkmin(int &a, int b) {
if(b < a) a = b;
}
int solve(string numbers, int i, int j, int s) {
if(memo[i][j][s] >= 0) return memo[i][j][s];
if(i == j) {
if (numbers[i]-'0' == s) return memo[i][j][s] = 0;
else return memo[i][j][s] = INF;
}
// the whole word match!
if(atoi(numbers.substr(i, j-i+1).c_str()) == s) return memo[i][j][s] = 0;
int res = INF;
for(int k = i; k < j; ++k) {
int left = atoi(numbers.substr(i,k-i+1).c_str());
if(left <= s){
//cout << numbers.substr(k+1, j-k+1) << "->" << s-left << endl;
int sol = 1+solve(numbers, k+1, j, s-left);
//cout << numbers.substr(k+1, j-k+1) << " (" << sol <<")" << endl;
checkmin(res, sol);
}
}
return memo[i][j][s] = res;
}
int QuickSums::minSums(string numbers, int sum) {
memset(memo, -1, sizeof(memo));
int res = solve(numbers, 0, numbers.length()-1, sum);
if(res == INF) return -1;
return res;
}
“ shortest(base)
if base is already a palindrome then
return base
if base has the form A...A then
return A + shortest(...) + A
if base has the form A...B then
return min(A + shortest(...B) + A,
B + shortest(A...) + B)
”
string memo[26][26];
string solve(string base, int i, int j) {
//cout << base.substr(i,j-i+1) << endl;
if(i>j) return string("");
if(i == j) return memo[i][j]=base[i];
if(memo[i][j] != "") return memo[i][j];
string res;
if(base[i] == base[j]) {
res = base[i] + solve(base, i+1, j-1)+base[i];
return memo[i][j]=res;
}
string pre = base[j] + solve(base, i, j-1) + base[j];
string suf = base[i] + solve(base, i+1, j) + base[i];
if(pre.length() != suf.length()) {
if(pre.length() < suf.length()) res = pre;
else res = suf;
}
else {
if(pre < suf) res = pre;
else res = suf;
}
return memo[i][j]=res;
}
string ShortPalindromes::shortest(string base) {
int L = base.length();
for(int i = 0; i < L; ++i)
for(int j = 0; j < L; ++j)
memo[i][j]="";
return solve(base, 0, base.length()-1);
}
long long memo[62][62][62];
int N;
long long solve(long long status, int i, int j, int f) {
if(memo[i][j][f] != -1LL) return memo[i][j][f];
if(f == 0 || (i == j && f == 1)) return memo[i][j][f] = 1LL;
if(i > j) return memo[i][j][f] = 0LL;
if(i == j && f > 1) return memo[i][j][f] = 0LL;
long long res = 0;
for(int k = i; k <= j; ++k) if(status & 1LL<<k) {
res += solve(status ^ (1LL<<k), k+2, j, f-1);
}
return memo[i][j][f] = res;
}
long long TreePlanting::countArrangements(int total, int fancy) {
memset(memo, -1, sizeof(memo));
N = total;
long long status = (1LL<<total)-1;
return solve(status, 0, total-1, fancy);
}
Editorial solution:
Here, we need to get a little creative to come up with a workable solution. Consider placing f fancy trees along a total of n locations, so that no two are adjacent. Call our function, C, the number of ways to do this. At our first location, we can either plant a fancy tree, or not plant a fancy tree. If we plant a fancy tree, then we can't plant a fancy tree in the second spot, and hence will have n-2 locations in which to plant the remaining f-1 fancy trees. If we don't plant a fancy tree in the first spot, then we have n-1 locations in which to place all f fancy trees. This gives us our recursive formula, C(n, f) = C(n - 2, f - 1) + C(n - 1, f). Our starting values are of course, C(1, 1) = 1, and C(0, 0) = 1.
However, with the problem constraints as they are, a simple recursive function by itself is not sufficient. We either need to implement memoization, whereby we store the values of previous recursive calls, to avoid recalculating them repeatedly, or we can use dynamic programming, as shown here:
public long countArrangements(int total, int fancy) {
long[][] count = new long[total + 1][fancy + 1];
count[0][0] = 1;
count[1][1] = 1;
for (int i = 0; i < = total; i++)
for (int j = 0; j < = fancy; j++) {
if (i > 0)
count[i][j] += count[i - 1][j];
if (i > 1 && j > 0)
count[i][j] += count[i - 2][j - 1];
};
return count[total][fancy];
}int diff(string& a, string& b) {
int cost = 0;
for(int i = 0;i < a.length(); ++i)
if(a[i]!=b[i]) cost ++;
return cost;
}
bool match(string& aa, string &bb) {
sort(ALL(aa));
return aa==bb;
}
int memo[52];//dict is a copy of validWords
//sort_dict is a copy of dict, but each row is sorted
vector<string> dict, sort_dict;
#define INF 999999999
int solve(int i, string &s) {
//cout << s.substr(i) << endl;
if(memo[i] != -1) return memo[i];
if(i == s.length()) return memo[i] = 0;
if(i > s.length()) return memo[i]=INF;
bool found = false;
int mincost = INF;
for(int k = 0; k < dict.size(); ++k) {
int len = dict[k].length();
if(!match(s.substr(i, len), sort_dict[k])) continue;
int ret = 0;
ret = solve(i+len, s);
if(ret == INF) continue;
else {
found = true;
ret += diff(s.substr(i, len), dict[k]);
}
mincost = min(mincost, ret);
}
if(found) return memo[i] = mincost;
return memo[i] = INF;
}
int SentenceDecomposition::decompose(string sentence, vector <string> validWords) {
sort_dict = dict = validWords;
for(int i = 0; i < sort_dict.size(); ++i)
sort(ALL(sort_dict[i]));
memset(memo, -1, sizeof(memo));
int res = solve(0, sentence);
if(res == INF) return -1;
return res;
}
