Sa computer science, ang isang problema ay sinasabing may magkakapatong na mga subproblema kung ang problema ay maaaring hatiin sa mga subproblema na ginagamit muli ng ilang beses o isang recursive algorithm para sa problema ay nalulutas ang parehong subproblema nang paulit-ulit sa halip na palaging bumubuo ng bago mga subproblema.
Ano ang pinakamainam na substructure at magkakapatong na subproblema sa dynamic na programming?
Ang isang problema ay may pinakamainam na katangian ng substructure kung ang isang pinakamainam na solusyon ng ibinigay na problema ay maaaring makuha sa pamamagitan ng paggamit ng pinakamainam na solusyon ng mga subproblema nito. Sinasamantala ng Dynamic Programming ang property na ito para makahanap ng solusyon.
Ano ang overlapping Subproblem sa dynamic programming?
1) Mga Overlapping na Subproblem:
Ang Dynamic na Programming ay pangunahing ginagamit kapag paulit-ulit na kailangan ang mga solusyon sa parehong mga subproblema. Sa dynamic na programming, ang mga nakalkulang solusyon sa mga subproblema ay iniimbak sa isang talahanayan upang ang mga ito ay hindi na kailangang muling kalkulahin.
Ano ang pagkakaiba sa pagitan ng pinakamainam na substructure at overlapping na subproblem?
Naiintindihan ko ang target na diskarte para sa parehong mga pamamaraan kung saan kinakalkula ng Optimal Substructure ang pinakamainam na solusyon batay sa isang input n habang tina-target ng Overlapping Subproblems ang lahat ng solusyon para sa hanay ng input, sabihin mula sa 1 hanggang n. Para sa problema tulad ng Rod Cutting Problem.
Alin sa mga Teknik na ito ang gumagamit ng overlapping ng mga subproblema?
Ang Dynamic Programming ay isang pamamaraan para sa paglutas ng mga problema sa mga magkakapatong na subproblema. Dito, iniimbak namin ang resulta ng sub-problema na nalutas nang isang beses para muling magamit sa hinaharap. Ang pamamaraan ng pag-iimbak ng mga sub-problem na solusyon ay tinatawag na memoization.
