📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    What does "optimal substructure" mean in the context of

    Dynamic Programming?
    A The problem can be divided into independent subproblems. Correct Answer Incorrect Answer
    B The optimal solution to the problem contains optimal solutions to its subproblems. Correct Answer Incorrect Answer
    C The problem has a unique optimal solution. Correct Answer Incorrect Answer
    D The problem can be solved by making locally optimal choices. Correct Answer Incorrect Answer
    E The problem's solution can be found in polynomial time. Correct Answer Incorrect Answer

    Solution

    Optimal substructure means that if an optimal solution to a problem contains an optimal solution to a subproblem, then the problem exhibits optimal substructure. This property is crucial for both Dynamic Programming and Greedy algorithms, as it allows us to build up the overall optimal solution from optimal solutions to smaller parts.

    Practice Next
    More IT Operating System Questions
    ask-question