This HTML5 document contains 33 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dcterms	http://purl.org/dc/terms/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
n14	https://global.dbpedia.org/id/
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
wikipedia-en	http://en.wikipedia.org/wiki/
dbc	http://dbpedia.org/resource/Category:
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
gold	http://purl.org/linguistics/gold/
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/

Statements

Subject Item

dbr:Partial_correlation

dbo:wikiPageWikiLink

dbr:Overlapping_subproblems

Subject Item

dbr:Algorithm

dbo:wikiPageWikiLink

dbr:Overlapping_subproblems

Subject Item

dbr:Algorithmic_technique

dbo:wikiPageWikiLink

dbr:Overlapping_subproblems

Subject Item

dbr:Longest_common_subsequence_problem

dbo:wikiPageWikiLink

dbr:Overlapping_subproblems

Subject Item

dbr:List_of_terms_relating_to_algorithms_and_data_structures

dbo:wikiPageWikiLink

dbr:Overlapping_subproblems

Subject Item

dbr:Overlapping_subproblems

rdf:type

dbo:Person

rdfs:label

Overlapping subproblems

rdfs:comment

In computer science, a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems. A naive recursive approach to such a problem generally fails due to an exponential complexity. If the problem also shares an optimal substructure property, dynamic programming is a good way to work it out.

dcterms:subject

dbc:Dynamic_programming

dbo:wikiPageID

1180800

dbo:wikiPageRevisionID

964753477

dbo:wikiPageWikiLink

dbr:Computer_science dbc:Dynamic_programming dbr:Recursive dbr:Optimal_substructure dbr:Fibonacci_sequence dbr:Memoization dbr:C_(programming_language) dbr:Computational_problem dbr:Fibonacci_number dbr:Dynamic_programming dbr:Exponential_time

owl:sameAs

freebase:m.04f11k wikidata:Q7113766 n14:4suuH

dbo:abstract

In computer science, a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems. For example, the problem of computing the Fibonacci sequence exhibits overlapping subproblems. The problem of computing the nth Fibonacci number F(n), can be broken down into the subproblems of computing F(n − 1) and F(n − 2), and then adding the two. The subproblem of computing F(n − 1) can itself be broken down into a subproblem that involves computing F(n − 2). Therefore, the computation of F(n − 2) is reused, and the Fibonacci sequence thus exhibits overlapping subproblems. A naive recursive approach to such a problem generally fails due to an exponential complexity. If the problem also shares an optimal substructure property, dynamic programming is a good way to work it out.

gold:hypernym

dbr:Times

prov:wasDerivedFrom

wikipedia-en:Overlapping_subproblems?oldid=964753477&ns=0

dbo:wikiPageLength

4707

foaf:isPrimaryTopicOf

wikipedia-en:Overlapping_subproblems

Subject Item

dbr:Overlapping_subproblem

dbo:wikiPageWikiLink

dbr:Overlapping_subproblems

dbo:wikiPageRedirects

dbr:Overlapping_subproblems

Subject Item

wikipedia-en:Overlapping_subproblems

foaf:primaryTopic

dbr:Overlapping_subproblems