Problems Without Optimal Substructure - Dynamic Programming

preview_player
Показать описание
Not all problems exhibit optimal substructure. We take a look at 2 such problems and see why they don't!
  1. CSBreakdown
  2. Dynamic Programming
  3. Optimal Substructure
  4. Computer Science (Field Of Study)
Рекомендации по теме
Problems Without Optimal 0:04:37

Problems Without Optimal Substructure - Dynamic Programming

Dynamic Programming | 0:02:17

Dynamic Programming | Set 2 (Optimal Substructure Property) | GeeksforGeeks

Dynamic Programming Is 0:01:00

Dynamic Programming Is Easy Once You Learn This... #dynamicprogramming #codinginterview #leetcode

Principle of Optimality 0:09:26

Principle of Optimality - Dynamic Programming

4.2 - Dynamic 0:30:28

4.2 - Dynamic Programming - Optimal Substructure

[Algorithms] Optimal substructure 0:07:45

[Algorithms] Optimal substructure of the activity selection problem

Dynamic Programming Is 0:01:00

Dynamic Programming Is EASY Once You Know This #codinginterview #dynamicprogramming #python

Optimal Similar Substructure 0:04:29

Optimal Similar Substructure - GT- Computability, Complexity, Theory: Algorithms

Proof of an 0:01:52

Proof of an Optimal substructure in Dynammic Programming? (2 Solutions!!)

[Algorithms] Optimal substructure 0:04:01

[Algorithms] Optimal substructure of a shortest path

Overlapping sub problems 0:06:01

Overlapping sub problems and Optimal Substructure in LCS | Dynamic Programming | Part 3

Can counting problems 0:02:03

Can counting problems have optimal substructure? (2 Solutions!!)

Why do we 0:01:31

Why do we need optimal substructure for dynamic programming?

4.1 - Optimal 0:39:10

4.1 - Optimal Substructure

[Algorithms] Optimal-substructure property 0:04:59

[Algorithms] Optimal-substructure property of the longest common subsequence problem

Optimal substructure 0:03:59

Optimal substructure

Optimal Substructure 0:09:46

Optimal Substructure

Introduction to Dynamic 0:08:41

Introduction to Dynamic Programming: Understanding Optimal Substructures

Optimal Substructure - 0:09:15

Optimal Substructure - Prerequisite for Dynamic Programming

4 Principle of 0:14:52

4 Principle of Optimality - Dynamic Programming introduction

Optimal Substructure property 0:04:26

Optimal Substructure property in Dynamic Programming

21. Bellman Ford 0:22:30

21. Bellman Ford Optimal Substructure

ICAPS 2017: Efficient 0:18:00

ICAPS 2017: Efficient motion planning for problems lacking optimal substructure

What is the 0:02:06

What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)?

Комментарии
Автор

Please, Please, Please we need more videos like this for the whole algorithm course. it is very helpful and your approach is easy and clear to follow. Thanks

TheImaginary
Автор

This series is really helpful, thanks for the work!

robyy_yyan
Автор

hi Karim,
Thanks for your DP videos. Which standard book, do you recommend for studying?

MrKishorebitta
Автор

I'm not sure I agree here that Maximal Clique problem does not have optimal substructure. Here you're looking only at one partition {1, 2, 3, 4, 5, 6, 7}, {8, 9}. The definition of optimal substructure is "optimal solutions to a problem incorporate optimal solutions to related subproblems, which we may solve independently." This doesn't mean any partition of subproblems but some particular set of subproblems. If we partition to {1, 2, 3, 4}, {5, 6, 7, 8, 9}. We get the optimal solution as maximum of two subproblems.

ikopysitsky