{"id":5107,"date":"2022-04-08T17:50:38","date_gmt":"2022-04-08T09:50:38","guid":{"rendered":"https:\/\/1989lifejourney.com\/?p=5107"},"modified":"2022-04-09T14:25:32","modified_gmt":"2022-04-09T06:25:32","slug":"difference-between-divide-and-conquer-and-dynamic-programming","status":"publish","type":"post","link":"https:\/\/1989lifejourney.com\/?p=5107","title":{"rendered":"Difference Between Divide and Conquer and Dynamic Programming"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Divide and conquer:<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u5efa\u57fa\u65bc\u591a\u9805\u5206\u652f\u905e\u8ff4\u7684\u4e00\u7a2e\u5f88\u91cd\u8981\u7684\u6f14\u7b97\u6cd5\u7bc4\u5f0f\u3002\u5b57\u9762\u4e0a\u7684\u89e3\u91cb\u662f\u300c\u5206\u800c\u6cbb\u4e4b\u300d\uff0c\u5c31\u662f\u628a\u4e00\u500b\u8907\u96dc\u7684\u554f\u984c\u5206\u6210\u5169\u500b\u6216\u66f4\u591a\u7684\u76f8\u540c\u6216\u76f8\u4f3c\u7684\u5b50\u554f\u984c\uff0c\u76f4\u5230\u6700\u5f8c\u5b50\u554f\u984c\u53ef\u4ee5\u7c21\u55ae\u7684\u76f4\u63a5\u6c42\u89e3\uff0c\u539f\u554f\u984c\u7684\u89e3\u5373\u5b50\u554f\u984c\u7684\u89e3\u7684\u5408\u4f75\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Dynamic programming:<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u901a\u904e\u628a\u539f\u554f\u984c\u5206\u89e3\u70ba\u76f8\u5c0d\u7c21\u55ae\u7684\u5b50\u554f\u984c\u7684\u65b9\u5f0f\u6c42\u89e3\u8907\u96dc\u554f\u984c\u7684\u65b9\u6cd5\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Difference between divide and conquer and dynamic programming:<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Divide and conquer combines the solutions of the sub-problems to obtain the solution of the main problem while dynamic programming uses the result of the sub-problems to find the optimum solution of the main problem.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Divide and Conquer Example: <\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>Binary search<\/li><li>Merge sort<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Dynamic programming Example:<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>Fibonacci\u6578\u5217<\/li><li>Longest Common Subsequence<\/li><li>Floyd-Warshall Algorithm<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Ref: <\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/pediaa.com\/what-is-the-difference-between-divide-and-conquer-and-dynamic-programming\/\">https:\/\/pediaa.com\/what-is-the-difference-between-divide-and-conquer-and-dynamic-programming\/<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/zh.wikipedia.org\/wiki\/%E5%88%86%E6%B2%BB%E6%B3%95\">https:\/\/zh.wikipedia.org\/wiki\/%E5%88%86%E6%B2%BB%E6%B3%95<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/zh.wikipedia.org\/wiki\/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92\">https:\/\/zh.wikipedia.org\/wiki\/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Divide and conquer: \u5efa\u57fa\u65bc\u591a\u9805\u5206\u652f\u905e\u8ff4\u7684\u4e00\u7a2e\u5f88\u91cd\u8981\u7684\u6f14\u7b97\u6cd5\u7bc4\u5f0f\u3002\u5b57\u9762\u4e0a\u7684\u89e3\u91cb\u662f\u300c\u5206\u800c\u6cbb\u4e4b\u300d [&hellip;]<\/p>\n","protected":false},"author":139426785,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_coblocks_attr":"","_coblocks_dimensions":"","_coblocks_responsive_height":"","_coblocks_accordion_ie_support":"","_postgate_lock_override":"inherit","_postgate_lock_mode":"inherit","_postgate_preview_mode":"inherit","_postgate_preview_limit":0,"_postgate_product_ids":[],"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":true,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_wpcom_ai_launchpad_first_post":false,"_jetpack_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[55138170,1],"tags":[],"post_folder":[],"class_list":["post-5107","post","type-post","status-publish","format-standard","hentry","category-technology-sharing","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/paR5vw-1kn","jetpack-related-posts":[{"id":13304,"url":"https:\/\/1989lifejourney.com\/?p=13304","url_meta":{"origin":5107,"position":0},"title":"Inside the Art Market: How It Works and How I See Art","author":"Kevin","date":"26 1 \u6708, 2026","format":false,"excerpt":"This is a PowerPoint presentation I made to introd\u2026","rel":"","context":"\u5728\u300cArt\u300d\u4e2d","block_context":{"text":"Art","link":"https:\/\/1989lifejourney.com\/?cat=177"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":8228,"url":"https:\/\/1989lifejourney.com\/?p=8228","url_meta":{"origin":5107,"position":1},"title":"Software team","author":"Kevin","date":"28 6 \u6708, 2023","format":false,"excerpt":"\u4e0d\u540c\u5de5\u7a0b\u5e2b\u968e\u5c64\u5b9a\u7fa9 Staff Engineer(or Principal Engineer or \u2026","rel":"","context":"\u5728\u300cTechnology sharing\u300d\u4e2d","block_context":{"text":"Technology sharing","link":"https:\/\/1989lifejourney.com\/?cat=55138170"},"img":{"alt_text":"","src":"https:\/\/mermaid.ink\/svg\/pako:eNqN00tvwjAMAOC_EuUM4s5hEs8xRsej2ynl4KWGZqQJMqkY6vjvS9NN2oMKcokbu58cKS65tCnyLt9oe5QZkGPPw8Qwv3oitht3BELWI5kph9KtWbt9x_pihpAyDbTFFpM232t89wHZw6HtEHLmazOjJGi2J_vmfzysa7QfgLkYaFukrKr9lViJPsgdmgupoRgrykM7_3IDEdlXpS9kRmJM1rj2RXImlr2fpy9iUXfLIjCwRaqv20tMnZ-Hz0W5IGWk2vvbjcxWGUQ61wWLquAjlhmmhcbOsgCt3KmzQq3A9-fjD7YsYzTKUmdaVNv5G18FPG7G4xvw5wZ8GPBJMz65bj802INgj5vt8Q2N3zfgo4BPm_HpdfuxwZ4FOyr9I6je8xcYXQef_oC8xXOkHFTqB6msmIS7DHNMeNeHKdAu4Ymp6qBwNj4ZybuOCmzxYp-Cw6GCLUHOuxvQB3-KqXKWonoyw4CePwECjDgq","width":350,"height":200,"srcset":"https:\/\/mermaid.ink\/svg\/pako:eNqN00tvwjAMAOC_EuUM4s5hEs8xRsej2ynl4KWGZqQJMqkY6vjvS9NN2oMKcokbu58cKS65tCnyLt9oe5QZkGPPw8Qwv3oitht3BELWI5kph9KtWbt9x_pihpAyDbTFFpM232t89wHZw6HtEHLmazOjJGi2J_vmfzysa7QfgLkYaFukrKr9lViJPsgdmgupoRgrykM7_3IDEdlXpS9kRmJM1rj2RXImlr2fpy9iUXfLIjCwRaqv20tMnZ-Hz0W5IGWk2vvbjcxWGUQ61wWLquAjlhmmhcbOsgCt3KmzQq3A9-fjD7YsYzTKUmdaVNv5G18FPG7G4xvw5wZ8GPBJMz65bj802INgj5vt8Q2N3zfgo4BPm_HpdfuxwZ4FOyr9I6je8xcYXQef_oC8xXOkHFTqB6msmIS7DHNMeNeHKdAu4Ymp6qBwNj4ZybuOCmzxYp-Cw6GCLUHOuxvQB3-KqXKWonoyw4CePwECjDgq 1x, https:\/\/mermaid.ink\/svg\/pako:eNqN00tvwjAMAOC_EuUM4s5hEs8xRsej2ynl4KWGZqQJMqkY6vjvS9NN2oMKcokbu58cKS65tCnyLt9oe5QZkGPPw8Qwv3oitht3BELWI5kph9KtWbt9x_pihpAyDbTFFpM232t89wHZw6HtEHLmazOjJGi2J_vmfzysa7QfgLkYaFukrKr9lViJPsgdmgupoRgrykM7_3IDEdlXpS9kRmJM1rj2RXImlr2fpy9iUXfLIjCwRaqv20tMnZ-Hz0W5IGWk2vvbjcxWGUQ61wWLquAjlhmmhcbOsgCt3KmzQq3A9-fjD7YsYzTKUmdaVNv5G18FPG7G4xvw5wZ8GPBJMz65bj802INgj5vt8Q2N3zfgo4BPm_HpdfuxwZ4FOyr9I6je8xcYXQef_oC8xXOkHFTqB6msmIS7DHNMeNeHKdAu4Ymp6qBwNj4ZybuOCmzxYp-Cw6GCLUHOuxvQB3-KqXKWonoyw4CePwECjDgq 1.5x, https:\/\/mermaid.ink\/svg\/pako:eNqN00tvwjAMAOC_EuUM4s5hEs8xRsej2ynl4KWGZqQJMqkY6vjvS9NN2oMKcokbu58cKS65tCnyLt9oe5QZkGPPw8Qwv3oitht3BELWI5kph9KtWbt9x_pihpAyDbTFFpM232t89wHZw6HtEHLmazOjJGi2J_vmfzysa7QfgLkYaFukrKr9lViJPsgdmgupoRgrykM7_3IDEdlXpS9kRmJM1rj2RXImlr2fpy9iUXfLIjCwRaqv20tMnZ-Hz0W5IGWk2vvbjcxWGUQ61wWLquAjlhmmhcbOsgCt3KmzQq3A9-fjD7YsYzTKUmdaVNv5G18FPG7G4xvw5wZ8GPBJMz65bj802INgj5vt8Q2N3zfgo4BPm_HpdfuxwZ4FOyr9I6je8xcYXQef_oC8xXOkHFTqB6msmIS7DHNMeNeHKdAu4Ymp6qBwNj4ZybuOCmzxYp-Cw6GCLUHOuxvQB3-KqXKWonoyw4CePwECjDgq 2x, https:\/\/mermaid.ink\/svg\/pako:eNqN00tvwjAMAOC_EuUM4s5hEs8xRsej2ynl4KWGZqQJMqkY6vjvS9NN2oMKcokbu58cKS65tCnyLt9oe5QZkGPPw8Qwv3oitht3BELWI5kph9KtWbt9x_pihpAyDbTFFpM232t89wHZw6HtEHLmazOjJGi2J_vmfzysa7QfgLkYaFukrKr9lViJPsgdmgupoRgrykM7_3IDEdlXpS9kRmJM1rj2RXImlr2fpy9iUXfLIjCwRaqv20tMnZ-Hz0W5IGWk2vvbjcxWGUQ61wWLquAjlhmmhcbOsgCt3KmzQq3A9-fjD7YsYzTKUmdaVNv5G18FPG7G4xvw5wZ8GPBJMz65bj802INgj5vt8Q2N3zfgo4BPm_HpdfuxwZ4FOyr9I6je8xcYXQef_oC8xXOkHFTqB6msmIS7DHNMeNeHKdAu4Ymp6qBwNj4ZybuOCmzxYp-Cw6GCLUHOuxvQB3-KqXKWonoyw4CePwECjDgq 3x"},"classes":[]},{"id":3895,"url":"https:\/\/1989lifejourney.com\/?p=3895","url_meta":{"origin":5107,"position":2},"title":"Functional Reactive Programming","author":"Kevin","date":"2 12 \u6708, 2021","format":false,"excerpt":"What is functional reactive programming (FRP)?FRP \u2026","rel":"","context":"\u5728\u300cIOS Development\u300d\u4e2d","block_context":{"text":"IOS Development","link":"https:\/\/1989lifejourney.com\/?cat=37324612"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":7176,"url":"https:\/\/1989lifejourney.com\/?p=7176","url_meta":{"origin":5107,"position":3},"title":"ChatGPT\u6e2c\u8a66 &#8211; how to become an iOS system architect","author":"Kevin","date":"7 3 \u6708, 2023","format":false,"excerpt":"\u4ee5\u4e0b\u70baChatGPT \u7684\u56de\u7b54\uff1a To become an iOS system architect,\u2026","rel":"","context":"\u5728\u300cTechnology sharing\u300d\u4e2d","block_context":{"text":"Technology sharing","link":"https:\/\/1989lifejourney.com\/?cat=55138170"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":11372,"url":"https:\/\/1989lifejourney.com\/?p=11372","url_meta":{"origin":5107,"position":4},"title":"\u5b8c\u7f8e\u4f34\u4fb6(Companion)\u96fb\u5f71\u5fc3\u5f97","author":"Kevin","date":"8 2 \u6708, 2025","format":false,"excerpt":"\u4eca\u5e74\u904e\u5e74\u8dd1\u53bb\u770b\u4e86\u9019\u90e8\u96fb\u5f71\uff0c\u539f\u672c\u60f3\u8aaa\uff0c\u9019\u500b\u96fb\u5f71\u7684\u5287\u60c5\u53ef\u80fd\u55ae\u7d14\u8b1b\u8ff0\u6a5f\u5668\u4eba\u8207\u4eba\u985e\u4e92\u52d5\u3002\u770b\u5b8c\u4e4b\u5f8c\uff0c\u767c\u73fe\u6709\u4e00\u4e9b\u2026","rel":"","context":"\u5728\u300cHobbies\u300d\u4e2d","block_context":{"text":"Hobbies","link":"https:\/\/1989lifejourney.com\/?cat=3281"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/02\/472835400_1018179490348913_7347511949614930409_n.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/02\/472835400_1018179490348913_7347511949614930409_n.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/02\/472835400_1018179490348913_7347511949614930409_n.jpg?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/02\/472835400_1018179490348913_7347511949614930409_n.jpg?resize=700%2C400&ssl=1 2x, https:\/\/i0.wp.com\/1989lifejourney.com\/wp-content\/uploads\/2025\/02\/472835400_1018179490348913_7347511949614930409_n.jpg?resize=1050%2C600&ssl=1 3x"},"classes":[]},{"id":12189,"url":"https:\/\/1989lifejourney.com\/?p=12189","url_meta":{"origin":5107,"position":5},"title":"App vs AI agent","author":"Kevin","date":"19 7 \u6708, 2025","format":false,"excerpt":"The first thing I did this morning was argue with \u2026","rel":"","context":"\u5728\u300cAI related\u300d\u4e2d","block_context":{"text":"AI related","link":"https:\/\/1989lifejourney.com\/?cat=763194612"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts\/5107","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/users\/139426785"}],"replies":[{"embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5107"}],"version-history":[{"count":6,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts\/5107\/revisions"}],"predecessor-version":[{"id":5121,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=\/wp\/v2\/posts\/5107\/revisions\/5121"}],"wp:attachment":[{"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5107"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5107"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5107"},{"taxonomy":"post_folder","embeddable":true,"href":"https:\/\/1989lifejourney.com\/index.php?rest_route=%2Fwp%2Fv2%2Fpost_folder&post=5107"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}