Блог пользователя cniks117

Автор cniks117, 11 лет назад, По-английски

how can we print all possible subsequences of string using dynamic programming. for ex . for sequence 1,2,3 the possible subsequences are {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

Теги dp
  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Here's the code how this could be done using recursion with caching. But, you can't do it faster than the number of all possible combinations:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<vector<string> > cache;
string s;
int n;

void subseq(int to)
{
	string tmp = "";
	for (int i = to - 1; i >= 0; i--)
	{
		if (cache[i].size() == 0)
			subseq(i);

		for (int j = 0; j < cache[i].size(); j++)
		{
			tmp = cache[i][j] + s[to - 1];
			cache[to].push_back(tmp);

			cout << tmp << endl;
		}
	}
}

int main()
{
	cin >> s;
	n = s.length();

	for (int i = 0; i <= n; i++)
		cache.push_back(vector<string>());
	cache[0].push_back("");

	subseq(n);

	return 0;
}