Decompose text to valid words (Word breaking)

Given a dictionary of valid words and an input text, write a function to check if the input text can be decomposed into valid words from dictionary.
Hint 1: use dynamic programming technique.
Hint 2: define T[k] is true if text[0...k] can be decomposed into valid words
Hint 3: T[k] is true if there exists any j : 0..k-1 where T[j] is true and text[j..k] is a valid word in dictionary.
This hints help us to write a simple loop to get the answer.

static string dic[4]={"bed","bath","beyond","and"};

bool decomps(string txt)
{
 map<string,bool> dm;
 for(int i=0;i<4;i++)
  dm[dic[i]]=true;
 vector<bool> t(txt.size()+1,false);
 t[0]=true;
 for(int k=1;k<=txt.size();k++)
 {
  bool candecomp=false;
  for(int i=0;i<k;i++)
  {
   string srch=txt.substr(i,k-i);
   map<string,bool>::iterator f=dm.find(srch);
   if(t[i]==true && f!=dm.end())
   {
    t[k]=true;
    break;
   }
  }
 }
 return t[txt.size()];
}
void  test_decomp()
{
 cout << decomps("bedbathandbeyond");
}

Min Coin Change problem using DP and backtracking

Suppose we have set of coins S={c1,c2,c3,...cn} and M
we need to find smallest number of coins to change M.
or find all <kj,cj> such that Sum ( kj*cj ) = M

Solution:
I used dynamic programming to solve the problem and also used backtracking to return all <kj,cj>:

for more information have a look at :
http://www.algorithmist.com/index.php/Min-Coin_Change

----------------------------------------------

map<int,int> min_coins(vector<int> pCoins,int pSum,int *pMinRequired)
{
 map<int,int> trace;//(pCoins.size());
 vector<int> mins(pSum+1);
 vector<int> prev(pSum+1);
 fill(mins.begin(),mins.end(),INFINITY);
 for(int i=0;i<pCoins.size();i++)
  trace.insert(make_pair<int,int>(pCoins[i],0));
 mins[0]=0;
 sort(pCoins.begin(),pCoins.end());
 for(int i=1;i<=pSum;i++)
 {
  int bestCoin=-1;
  for(int v=0;v<pCoins.size() && pCoins[v]<=i  ;v++)
   if(mins[i-pCoins[v]]+1<mins[i])
   {
    mins[i]=mins[i-pCoins[v]]+1;
    bestCoin=v;
    prev[i]=i-pCoins[v];
   }
   if(bestCoin !=-1)
    trace[i]=pCoins[bestCoin];
 }
 *pMinRequired= mins[pSum];
 int curr=pSum;
 map<int,int> ret;
 while(curr>0)
 {
  ret[trace[curr]]++;
  curr=prev[curr];
 }
 return  ret;
}

 void test_coins()
{
 vector<int> coins;
 coins.push_back(1);
 coins.push_back(5);
 coins.push_back(10);
 coins.push_back(25);
 int minreq,sum=30;
 map<int,int> result=min_coins(coins,sum,&minreq);
 cout << " min required for "<<sum<<"$ is to pick "<<minreq<<" coins as :"<<endl;
 for(map<int,int>::iterator it=result.begin();it!=result.end();it++)
  cout <<" pick "<<it->second <<" coins of "<<it->first<<endl;

}

---------------------------------------------