Динамическое программирование С++

[Александр222]

Нужно решить динамическим программированием с использованием запоминания и рекурсивным спуском
Screenshot_20210504_041420.jpg

[Александр222]

Решение этой задачи ниже. (метод динамического программирования)
Кто-нибудь может расссказать о рекрсивном спуске? Где, что почитать. Потому что все, что я имею сейчас, это небольшой пример ниже.

Решение методом динамического программирования:

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


double minPoly( const string &S, double x )
{
   int LEN = S.size();

   vector< vector< vector<double> > > P( LEN, vector< vector<double> >( LEN, vector<double>( LEN, 0.0 ) ) );

   for ( int i = 0; i < LEN; i++ ) P[i][i][0] = S[i] - '0';                   

   for ( int run = 2; run <= LEN; run++ )                                   
   {                                                 
      for ( int i = 0, j = i + run - 1; i <= LEN - run; i++, j++ )          
      {
         P[i][j][0] = 10 * P[i][j-1][0] + P[j][j][0];                         
         for ( int deg = 1; deg < run; deg++ )                             
         {
            P[i][j][deg] = P[i][i][0] + x * P[i+1][j][deg-1];                 
            for ( int c = i + 1; c < j - deg + 1; c++ ) P[i][j][deg] = min( P[i][j][deg], P[i][c][0] + x * P[c+1][j][deg-1] );
         }
      }
   }

   return *min_element( P[0][LEN-1].begin(), P[0][LEN-1].begin()+LEN );       
}


int main()
{
   string S;
   double x;
   cout << "Input S: ";   cin >> S;
   cout << "Input x: ";   cin >> x;
   cout << "Minimum polynomial is " << minPoly( S, x ) << '\n';
}

Пример рекурсивного спуска:

#include <iostream>
#include <list>

using namespace std;

list<string> get_subdirs(const string &path)
{
    // какая-то реализация получения списка каталогов, зависимая от ОС
}

string path_concat(const string &path, const string &name)
{
    // какая-то реализация склеивания пути с именем, напр.: C:\\Users + Admin = C:\\Users\\Admin
}

string indent(int level)
{
    // сформировать отступ
    string result;
    for (size_t i = 0 ; i < level; ++i)
        result += '-';

    return result;
}

void print_directory(const string &path, int level = 1)
{
    list<string> subdirs = get_subdirs(path);

    for (list<string>::iterator it = subdirs.begin(); it != subdirs.end(); ++it)
    {
        string dir = *it;
        cout << indent(level) << dir << endl;
        print_directory(path_concat(path, dir), level + 1);
    }
}

int main(int argc, char *argv[])
{
    print_directory("C:\\");
    return 0;
}