Krótko, konkretnie, technicznie — notatki z praktyki.
Wprowadzam pojęcie programowania dynamicznego i pokazuję, jak zastosować go do rozwiązania problemu Longest Common Subsequence. Przedstawiam koncepcję rozdzielania problemu na mniejsze części i wykorzystywania wyników tych części do uzyskania rozwiązania głównego. Na przykładzie ilustruję, jak wykorzystać wiedzę o najdłuższych wspólnych podciągach do obliczenia najdłuższego wspólnego podciągu dla dwoch ciągów znaków.
Wprowadzam pojęcie programowania dynamicznego i pokazuję, jak zastosować go do rozwiązania problemu Longest Increasing Sequence. Przedstawiam koncepcję rozdzielania problemu na mniejsze części i wykorzystywania wyników tych części do uzyskania rozwiązania głównego. Na przykładzie ilustruję, jak wykorzystać wiedzę o najdłuższych podciągach do obliczenia najdłuższego podciągu po dodaniu nowego elementu do ciągu.
Na klasycznym zadaniu z cyklem w liście jednokierunkowej porównuję kilka podejść: z dodatkowymi strukturami danych, z modyfikacją listy oraz algorytm „żółwia i zająca” Floyd’a. Omawiam złożoność, zużycie pamięci i praktyczne zalety każdego rozwiązania.
Analizuję różne sposoby liczenia ustawionych bitów w liczbie całkowitej: od prostego przesuwania i maskowania, aż po wykorzystanie tablic pomocniczych. Porównuję czytelność, wydajność i zastosowania w praktyce.