{"id":15126,"date":"2022-04-17T08:43:47","date_gmt":"2022-04-17T07:43:47","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=15126"},"modified":"2024-02-11T15:50:58","modified_gmt":"2024-02-11T14:50:58","slug":"ex-programmation-dynamique","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/","title":{"rendered":"16 Answer Key Exercises Dynamic Programming and Divide and Conquer"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"15126\" class=\"elementor elementor-15126\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2814c23 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2814c23\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-8e2e36d\" data-id=\"8e2e36d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6c8deb3 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"6c8deb3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/algorithmique\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algorithmique<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-cae20cd\" data-id=\"cae20cd\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-361571c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"361571c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/algorithmique\/corrected-exercises-algorithms\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-f44ee36\" data-id=\"f44ee36\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f68bc24 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f68bc24\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Algorithm\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5102415 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5102415\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-08701aa\" data-id=\"08701aa\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-154aee9 elementor-widget elementor-widget-text-editor\" data-id=\"154aee9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f78f59d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f78f59d\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ce31526\" data-id=\"ce31526\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-e5a5f25 elementor-widget elementor-widget-heading\" data-id=\"e5a5f25\" data-element_type=\"widget\" data-widget_type=\"heading.default\"><div class=\"elementor-widget-container\"><div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercices-corriges-sur-la-programmation-dynamique\" >Exercices corrig\u00e9s sur la programmation dynamique<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-1\" >Exercice 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-2\" >Exercice 2<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-3\" >Exercice 3<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-4\" >Exercice 4<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-5\" >Exercice 5<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-6\" >Exercice 6<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-7\" >Exercice 7<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-8\" >Exercice 8<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-9\" >Exercice 9<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-10\" >Exercice 10<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-11\" >Exercice 11<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-12\" >Exercice 12<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-13\" >Exercice 13<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-15\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-14\" >Exercice 14<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-16\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-15\" >Exercice 15<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-17\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-conquer-and-dynamic-programming\/#Exercice-16\" >Exercice 16<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-sur-la-programmation-dynamique\"><\/span>Exercices corrig\u00e9s sur la programmation dynamique<span class=\"ez-toc-section-end\"><\/span><\/h2><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section><section class=\"elementor-section elementor-top-section elementor-element elementor-element-e0b2cbc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e0b2cbc\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8fa0eba\" data-id=\"8fa0eba\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-8aae2f1 elementor-widget elementor-widget-text-editor\" data-id=\"8aae2f1\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\"><div class=\"elementor-widget-container\"><div class=\"elementor-text-editor elementor-clearfix\"><p>Cette page propose plusieurs exercices corrig\u00e9s de <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/dynamic-programming\/\">programmation dynamique<\/a> et <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-rule\/\">diviser pour r\u00e9gner<\/a>.\u00a0 L&rsquo;objectif est de comprendre la diff\u00e9rence entre le paradigme Divide &amp; Conquer (Diviser pour r\u00e9gner) et la programmation dynamique. Les sp\u00e9cificit\u00e9s de la <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/\">recherche de chemin<\/a> (plus court chemin), probl\u00e8me de <a href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/\">planification<\/a>, probl\u00e8me de flot maximum et plus g\u00e9n\u00e9ralement la <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">th\u00e9orie des graphes<\/a> est trait\u00e9e \u00e0 part.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"Diviser pour r\u00e9gner et la programmation dynamique\" width=\"97\" height=\"97\" title=\"\"><\/p><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fb0ecd0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fb0ecd0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-07a3dd9\" data-id=\"07a3dd9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ef0f5d6 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"ef0f5d6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-38274f1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"38274f1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-294421c\" data-id=\"294421c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3a82099 elementor-widget elementor-widget-heading\" data-id=\"3a82099\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Exercice 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ffb2b78 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ffb2b78\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d322114\" data-id=\"d322114\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-545ae2f elementor-widget elementor-widget-text-editor\" data-id=\"545ae2f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9crivez un pseudo-code pour un algorithme de type diviser pour r\u00e9gner permettant de trouver la position du plus grand \u00e9l\u00e9ment dans un tableau de nombres. \u00c9crivez un pseudo-code pour un algorithme de force brute, comparez avec le pr\u00e9c\u00e9dent. Montrez un <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">arbre<\/a> du processus de l&rsquo;algorithme diviser pour mieux r\u00e9gner. Quel est le niveau maximal de l&rsquo;arborescence pour les nombres&nbsp;?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4af348a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4af348a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7bac323\" data-id=\"7bac323\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ee7ab5c elementor-widget elementor-widget-toggle\" data-id=\"ee7ab5c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2501\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2501\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2501\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2501\"><p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-11032 size-full\" title=\"Corrected Exercises: Algorithms 1\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image42.png\" alt=\"diviser pour r\u00e9gner programmation dynamique exercices corrig\u00e9s\" width=\"522\" height=\"209\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image42.png 522w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image42-300x120.png 300w\" sizes=\"(max-width: 522px) 100vw, 522px\" \/><\/p><p>L&rsquo;algorithme de force brute est trivial : une boucle.<\/p><p>A chaque niveau l, l&rsquo;arbre binaire complet est compos\u00e9 de 2^(l-1) feuille. Donc le total des sommets est 2^l -1. Soit l le niveau de l&rsquo;arbre, donc l=sup(log_2 (n)).<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-393fdb6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"393fdb6\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4c8f4b5\" data-id=\"4c8f4b5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4e53341 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"4e53341\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e1f21f5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e1f21f5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c223866\" data-id=\"c223866\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0024e97 elementor-widget elementor-widget-heading\" data-id=\"0024e97\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Exercice 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ef70904 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ef70904\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-aa56bc5\" data-id=\"aa56bc5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a8edb5d elementor-widget elementor-widget-text-editor\" data-id=\"a8edb5d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\tOn vous donne un tableau avec des entiers (positif, n\u00e9gatif, z\u00e9ro) et vous \u00eates cens\u00e9 trouver la somme contigu\u00eb maximale dans ce tableau. Par cons\u00e9quent, vous devez trouver un sous-tableau qui donne la plus grande somme. Exemple, si le tableau donn\u00e9 est : 5, -6, 7, 12, -3, 0, -11, -6\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b70d224 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b70d224\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ea60cb7\" data-id=\"ea60cb7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2dba5c0 elementor-widget elementor-widget-toggle\" data-id=\"2dba5c0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-4791\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-4791\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-4791\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-4791\"><p>Supposons que votre tableau d&rsquo;entr\u00e9e s&rsquo;appelle A. Ce que vous devez faire est de former un autre tableau, disons B, dont chaque valeur i est calcul\u00e9e en utilisant la formule r\u00e9cursive, max(A[i], B[i-1]+A[i ])<\/p><p>Ce que vous faites effectivement, c&rsquo;est que vous choisissez d&rsquo;\u00e9tendre la fen\u00eatre pr\u00e9c\u00e9dente ou d&rsquo;en d\u00e9marrer une nouvelle. Vous pouvez le faire puisque vous n&rsquo;\u00eates cens\u00e9 s\u00e9lectionner que des \u00e9l\u00e9ments continus dans le cadre de vos sous-ensembles.<\/p><p>5, -6, 7, 12, -3, 0, -11, -6<\/p><p>La r\u00e9ponse serait 19 (du sous-tableau {7,12} )<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9341960 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9341960\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-704223b\" data-id=\"704223b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5444200 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"5444200\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-53fd743 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"53fd743\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-22d5869\" data-id=\"22d5869\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bb4608c elementor-widget elementor-widget-heading\" data-id=\"bb4608c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Exercice 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-80fd13f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"80fd13f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3c4d88d\" data-id=\"3c4d88d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c251c2f elementor-widget elementor-widget-text-editor\" data-id=\"c251c2f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Utilisez la sous-cha\u00eene commune la plus longue pour : BDCABA et ABCBDAB. L&rsquo;algorithme est d\u00e9crit comme suit:<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-11034 size-full\" title=\"Corrected Exercises: Algorithms 3\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image43.png\" alt=\"diviser pour r\u00e9gner programmation dynamique exercices corrig\u00e9s sous-cha\u00eene commune\" width=\"718\" height=\"438\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image43.png 718w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image43-300x183.png 300w\" sizes=\"(max-width: 718px) 100vw, 718px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-232ba0f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"232ba0f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4ba7cd2\" data-id=\"4ba7cd2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-eceb922 elementor-widget elementor-widget-toggle\" data-id=\"eceb922\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2481\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2481\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2481\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2481\"><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-11035 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image44.png\" alt=\"diviser pour r\u00e9gner programmation dynamique exercices corrig\u00e9s sous-cha\u00eene commune\" width=\"760\" height=\"520\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image44.png 760w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image44-300x205.png 300w\" sizes=\"(max-width: 760px) 100vw, 760px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a435d9e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a435d9e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1881d13\" data-id=\"1881d13\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-af3b04b elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"af3b04b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1f1c932 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1f1c932\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8b9a965\" data-id=\"8b9a965\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2810be6 elementor-widget elementor-widget-heading\" data-id=\"2810be6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-4\"><\/span>Exercice 4<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d4ad414 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d4ad414\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4484de4\" data-id=\"4484de4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-10a7590 elementor-widget elementor-widget-text-editor\" data-id=\"10a7590\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Adaptez la sous-cha\u00eene commune la plus longue \u00e0 la sous-s\u00e9quence commune la plus longue\u00a0: BDCABA et ABCBDAB. Le probl\u00e8me de la plus longue sous-s\u00e9quence commune (LCS) consiste \u00e0 trouver la plus longue sous-s\u00e9quence commune \u00e0 toutes les s\u00e9quences d&rsquo;un ensemble de s\u00e9quences (souvent seulement deux s\u00e9quences).<\/p><p>Cela diff\u00e8re des probl\u00e8mes de recherche de sous-cha\u00eenes communes : contrairement aux sous-cha\u00eenes, les sous-s\u00e9quences ne sont pas oblig\u00e9es d&rsquo;occuper des positions cons\u00e9cutives dans les s\u00e9quences d&rsquo;origine.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7f155ad elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7f155ad\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a04b06f\" data-id=\"a04b06f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-48c8ea1 elementor-widget elementor-widget-toggle\" data-id=\"48c8ea1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-7631\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-7631\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-7631\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-7631\"><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-11036 size-full\" title=\"Corrected Exercises: Algorithms 5\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image46.png\" alt=\"diviser pour r\u00e9gner programmation dynamique exercices corrig\u00e9s sous-s\u00e9quence maximum\" width=\"658\" height=\"108\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image46.png 658w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image46-300x49.png 300w\" sizes=\"(max-width: 658px) 100vw, 658px\" \/><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-11037 size-full\" title=\"Corrected Exercises: Algorithms 6\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image47.png\" alt=\"diviser pour r\u00e9gner programmation dynamique exercices corrig\u00e9s sous-s\u00e9quence maximum\" width=\"324\" height=\"361\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image47.png 324w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image47-269x300.png 269w\" sizes=\"(max-width: 324px) 100vw, 324px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a2b6fad elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a2b6fad\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f797982\" data-id=\"f797982\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-75ec244 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"75ec244\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-04c0b80 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"04c0b80\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-9393c14\" data-id=\"9393c14\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-70731c3 elementor-widget elementor-widget-heading\" data-id=\"70731c3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-5\"><\/span>Exercice 5<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9a9a571 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9a9a571\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c8c4dca\" data-id=\"c8c4dca\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-311852c elementor-widget elementor-widget-text-editor\" data-id=\"311852c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>La distance de Levenshtein est une m\u00e9trique de cha\u00eene permettant de mesurer la diff\u00e9rence entre deux s\u00e9quences. De mani\u00e8re informelle, la distance de Levenshtein entre deux mots est le nombre minimum de modifications d&rsquo;un seul caract\u00e8re (c&rsquo;est-\u00e0-dire des insertions, des suppressions ou des substitutions) n\u00e9cessaires pour changer un mot en l&rsquo;autre. Proposer un programme dynamique pour r\u00e9soudre ce probl\u00e8me. Essai avec MEILENSTEIN et LEVENSHTEIN.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6ede0f5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6ede0f5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e4ab0e7\" data-id=\"e4ab0e7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a7e619d elementor-widget elementor-widget-toggle\" data-id=\"a7e619d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1761\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1761\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1761\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1761\"><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-11038 size-full\" title=\"Corrected Exercises: Algorithms 7\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image48.png\" alt=\"diviser pour r\u00e9gner programmation dynamique exercices corrig\u00e9s distance de Levenshtein\" width=\"587\" height=\"110\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image48.png 587w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image48-300x56.png 300w\" sizes=\"(max-width: 587px) 100vw, 587px\" \/><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-11039 size-full\" title=\"Corrected Exercises: Algorithms 8\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image49.png\" alt=\"diviser pour r\u00e9gner programmation dynamique exercices corrig\u00e9s distance de Levenshtein\" width=\"392\" height=\"260\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image49.png 392w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image49-300x199.png 300w\" sizes=\"(max-width: 392px) 100vw, 392px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-504a792 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"504a792\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d695204\" data-id=\"d695204\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8df6116 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"8df6116\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8fc37a6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8fc37a6\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-70388aa\" data-id=\"70388aa\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-08cd7ff elementor-widget elementor-widget-heading\" data-id=\"08cd7ff\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-6\"><\/span>Exercice 6<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-101f809 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"101f809\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b029b3e\" data-id=\"b029b3e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-cefb328 elementor-widget elementor-widget-text-editor\" data-id=\"cefb328\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Alice et Bob jouent \u00e0 tour de r\u00f4le \u00e0 un jeu, Alice commen\u00e7ant en premier.<\/p><p>Initialement, il y a un nombre n au tableau. Au tour de chaque joueur, ce joueur effectue un coup consistant en :<\/p><p>Choisir n&rsquo;importe quel x avec 0 &lt; x &lt; n et n % x == 0.<br \/>Remplacer le nombre n au tableau par n &#8211; x.<br \/>De plus, si un joueur ne peut pas bouger, il perd la partie.<\/p><p>Renvoyer vrai si et seulement si Alice gagne la partie, en supposant que les deux joueurs jouent de mani\u00e8re optimale.<\/p><p>Exemple 1:<\/p><p>Entr\u00e9e : n = 2<br \/>Sortie\u00a0: vrai<br \/>Explication : Alice choisit 1 et Bob n&rsquo;a plus de coups.<\/p><p>Exemple 2\u00a0:<\/p><p>Entr\u00e9e : n = 3<br \/>Sortie\u00a0: faux<br \/>Explication : Alice choisit 1, Bob choisit 1 et Alice n&rsquo;a plus de coups.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e2cb907 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e2cb907\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-6f3cc33\" data-id=\"6f3cc33\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ddd850d elementor-widget elementor-widget-toggle\" data-id=\"ddd850d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2321\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2321\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2321\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2321\"><p>Pour r\u00e9pondre \u00e0 ce probl\u00e8me, nous allons construire un tableau de solution. dp[i] indique le r\u00e9sultat du jeu pour le nombre donn\u00e9 i et pour le joueur qui a commenc\u00e9 la partie. Alice essaiera tous les facteurs et choisira celui qui donne \u00e0 son adversaire une valeur perdante.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19346 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame.png\" alt=\"divisor game\" width=\"342\" height=\"384\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame.png 342w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame-267x300.png 267w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame-11x12.png 11w\" sizes=\"(max-width: 342px) 100vw, 342px\" \/><\/p><p>Il est aussi possible de r\u00e9soudre ce probl\u00e8me de mani\u00e8re r\u00e9cursive plus classique, appel\u00e9 Top-Down.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19347 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame2.png\" alt=\"divisor game\" width=\"325\" height=\"311\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame2.png 325w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame2-300x287.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame2-13x12.png 13w\" sizes=\"(max-width: 325px) 100vw, 325px\" \/><\/p><p>Et pour un c\u00f4t\u00e9 plus pratique nous allons ajouter une m\u00e9mo\u00efsation.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19348 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame3.png\" alt=\"divisor game\" width=\"350\" height=\"557\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame3.png 350w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame3-189x300.png 189w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/divisorgame3-8x12.png 8w\" sizes=\"(max-width: 350px) 100vw, 350px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d1e7f6b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d1e7f6b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-94f3329\" data-id=\"94f3329\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6379957 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"6379957\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f084ddb elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f084ddb\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f0b1b0f\" data-id=\"f0b1b0f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7e0ce19 elementor-widget elementor-widget-heading\" data-id=\"7e0ce19\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-7\"><\/span>Exercice 7<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5c8e4d9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5c8e4d9\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8621dc6\" data-id=\"8621dc6\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4473d82 elementor-widget elementor-widget-text-editor\" data-id=\"4473d82\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>On vous donne un co\u00fbt de tableau d&rsquo;entiers o\u00f9 co\u00fbt[i] est le co\u00fbt de la i\u00e8me marche d&rsquo;un escalier. Une fois que vous avez pay\u00e9 le co\u00fbt, vous pouvez monter une ou deux marches.<\/p><p>Vous pouvez soit d\u00e9marrer \u00e0 partir de l&rsquo;\u00e9tape avec l&rsquo;indice 0, soit \u00e0 partir de l&rsquo;\u00e9tape avec l&rsquo;indice 1.<\/p><p>Renvoyez le co\u00fbt minimum pour atteindre le sommet de l&rsquo;\u00e9tage.<\/p><p>Exemple 1:<\/p><p>Entr\u00e9e : co\u00fbt = [10,15,20]<br \/>Sortie\u00a0: 15<\/p><p>Explication : Vous commencerez \u00e0 l&rsquo;index 1.<br \/>&#8211; Payez 15 et montez deux marches pour atteindre le sommet.<br \/>Le co\u00fbt total est de 15.<\/p><p>Exemple 2\u00a0:<\/p><p>Entr\u00e9e : co\u00fbt = [1,100,1,1,1,100,1,1,100,1]<br \/>Sortie\u00a0: 6<\/p><p>Explication : Vous commencerez \u00e0 l&rsquo;index 0.<br \/>&#8211; Payez 1 et montez deux marches pour atteindre l&rsquo;indice 2.<br \/>&#8211; Payez 1 et montez deux marches pour atteindre l&rsquo;indice 4.<br \/>&#8211; Payez 1 et montez deux marches pour atteindre l&rsquo;indice 6.<br \/>&#8211; Payez 1 et montez d&rsquo;une marche pour atteindre l&rsquo;indice 7.<br \/>&#8211; Payez 1 et montez deux marches pour atteindre l&rsquo;indice 9.<br \/>&#8211; Payez 1 et montez une marche pour atteindre le sommet.<br \/>Le co\u00fbt total est de 6.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ee1e2e1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ee1e2e1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-535cad1\" data-id=\"535cad1\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2e351fe elementor-widget elementor-widget-toggle\" data-id=\"2e351fe\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-4841\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-4841\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-4841\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-4841\"><p>Pour un premier jet, nous allons r\u00e9soudre ce probl\u00e8me en <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/recursive-programming\/\">r\u00e9cursif<\/a>. Pour cela nous gardons en m\u00e9moire le plus petit co\u00fbt en consid\u00e9rant que l&rsquo;on fasse marche arri\u00e8re d&rsquo;une marche et de deux marches. Et ainsi de suite jusqu&rsquo;\u00e0 avoir le co\u00fbt de la premi\u00e8re ou deuxi\u00e8me marche.<\/p><p><code>mincost(0) = cost[0]<\/code><br \/><code>mincost(1) = cost[1]<\/code><\/p><p>mincost(i) = cost[i]+min(mincost(i-1), mincost(i-2))<\/p><p>Ce qui donne le code suivant :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19349 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs.png\" alt=\"climbing stairs\" width=\"512\" height=\"211\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs.png 512w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs-300x124.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs-18x7.png 18w\" sizes=\"(max-width: 512px) 100vw, 512px\" \/><\/p><p>Dans un second temps, nous allons rester en approche top-down et ajouter un syst\u00e8me de m\u00e9mo\u00efsation. Ainsi, un minCost d\u00e9j\u00e0 trouver ne sera pas recalculer par la suite.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19350 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs2.png\" alt=\"climbing stairs\" width=\"521\" height=\"315\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs2.png 521w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs2-300x181.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs2-18x12.png 18w\" sizes=\"(max-width: 521px) 100vw, 521px\" \/><\/p><p>Enfin, nous allons prendre le probl\u00e8me en bottom-up pour faire de la programmation dynamique;<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19351 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs3.png\" alt=\"climbing stairs\" width=\"428\" height=\"213\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs3.png 428w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs3-300x149.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/climbingstairs3-18x9.png 18w\" sizes=\"(max-width: 428px) 100vw, 428px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-36a9ff0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"36a9ff0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-31f3481\" data-id=\"31f3481\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8766493 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"8766493\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-78fbcf2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"78fbcf2\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1f5c595\" data-id=\"1f5c595\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fa94e76 elementor-widget elementor-widget-heading\" data-id=\"fa94e76\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-8\"><\/span>Exercice 8<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1fa75ac elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1fa75ac\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5c2f478\" data-id=\"5c2f478\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-53b0553 elementor-widget elementor-widget-text-editor\" data-id=\"53b0553\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Alice et Bob jouent \u00e0 un jeu avec des tas de pierres. Il y a un nombre pair de piles dispos\u00e9es dans une rang\u00e9e, et chaque pile a un nombre entier positif de piles de pierres[i].<\/p><p>L&rsquo;objectif du jeu est de terminer avec le plus de pierres. Le nombre total de pierres sur toutes les piles est impair, il n&rsquo;y a donc pas d&rsquo;\u00e9galit\u00e9.<\/p><p>Alice et Bob se relaient, Alice commen\u00e7ant en premier. A chaque tour, un joueur prend toute la pile de pierres soit depuis le d\u00e9but soit depuis la fin de la rang\u00e9e. Cela continue jusqu&rsquo;\u00e0 ce qu&rsquo;il n&rsquo;y ait plus de piles, \u00e0 quel point la personne avec le plus de pierres gagne.<\/p><p>En supposant qu&rsquo;Alice et Bob jouent de mani\u00e8re optimale, renvoyez true si Alice gagne la partie, ou false si Bob gagne.<\/p><p>Entr\u00e9e :\u00a0pierres = [5,3,4,5]<br \/>Sortie\u00a0: vrai<\/p><p>Alice commence en premier et ne peut prendre que les 5 premiers ou les 5 derniers.<br \/>Disons qu&rsquo;elle prend les 5 premiers, de sorte que la ligne devient [3, 4, 5].<br \/>Si Bob prend 3, alors le tableau est [4, 5], et Alice prend 5 pour gagner avec 10 points.<br \/>Si Bob prend les 5 derniers, alors le tableau est [3, 4], et Alice prend 4 pour gagner avec 9 points.<\/p><p>Cela a d\u00e9montr\u00e9 que prendre les 5 premiers \u00e9tait un coup gagnant pour Alice, nous retournons donc vrai.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-38cb91b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"38cb91b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-76e4266\" data-id=\"76e4266\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4365458 elementor-widget elementor-widget-toggle\" data-id=\"4365458\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-7061\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-7061\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-7061\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-7061\"><p>Commen\u00e7ons par une approche top-down avec m\u00e9mo\u00efsation.<\/p><ul><li>Veuillez noter que les deux joueurs jouent de mani\u00e8re optimale, nous jouons donc de mani\u00e8re optimale, peu importe qui est Alice, qui est Bob.<\/li><li>Soit dp(left, right) return [firstScore, secondScore] o\u00f9 firstScore est le score maximum lorsque le joueur1 joue en premier, secondScore est le score maximum lorsque le joueur2 joue en second, il ramasse des pierres en piles[left]&#8230;piles[right ].<\/li><li>Pour les pierres en tas[left]&#8230;piles[right], il y a 2 choix pour le joueur1 \u00e0 choisir\u00a0:<ul><li>Choisissez \u00e0 gauche : pickLeft = dp(gauche + 1, droite).<ul><li>Le score du joueur1 = piles[left] + le score du deuxi\u00e8me choix de pickLeft, donc firstScore = piles[left] + pickLeft[1]<\/li><li>Le score du joueur2 = score du premier choix de pickLeft, donc secondScore = pickLeft[0]<\/li><\/ul><\/li><li>Choisir \u00e0 droite : pickRight = dp(gauche, droite &#8211; 1).<ul><li>Le score du joueur1 = piles[right] + le deuxi\u00e8me score de pickRight, donc firstScore = piles[right] + pickRight[1]<\/li><li>Le score du joueur2 = score du premier choix de pickRight, donc secondScore = pickRight[0].<\/li><\/ul><\/li><\/ul><\/li><li>Nous devons obtenir le score maximum lorsque le joueur 1 joue en premier parmi plus de 2 choix.<\/li><li>Enfin, dp(0, len(piles) &#8211; 1) return [firstScore, secondScore], o\u00f9 alexScore = firstScore puisque Alice joue en premier, leeScore = secondScore puisque Bob joue en second.<\/li><\/ul><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19352 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/stonegame.png\" alt=\"stone game\" width=\"569\" height=\"304\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/stonegame.png 569w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/stonegame-300x160.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/stonegame-18x10.png 18w\" sizes=\"(max-width: 569px) 100vw, 569px\" \/><\/p><p>Maintenant on va faire un algorithme en bottom-up en gardant la m\u00e9mo\u00efsation. Ainsi l&rsquo;algorithme sera en programmation dynamique.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19353 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/stonegame2.png\" alt=\"stone game\" width=\"607\" height=\"415\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/stonegame2.png 607w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/stonegame2-300x205.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/stonegame2-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/stonegame2-600x410.png 600w\" sizes=\"(max-width: 607px) 100vw, 607px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-13261dc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"13261dc\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b3f4554\" data-id=\"b3f4554\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b871841 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"b871841\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-41c940b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"41c940b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0b851c2\" data-id=\"0b851c2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e8e1dd9 elementor-widget elementor-widget-heading\" data-id=\"e8e1dd9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-9\"><\/span>Exercice 9<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-241ab9a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"241ab9a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d8874dc\" data-id=\"d8874dc\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1150c7e elementor-widget elementor-widget-text-editor\" data-id=\"1150c7e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Il y a n soldats debout en ligne. Chaque soldat se voit attribuer une valeur de classement unique.<\/p><p>Vous devez former une \u00e9quipe de 3 soldats parmi eux selon les r\u00e8gles suivantes :<\/p><p>Choisissez 3 soldats avec l&rsquo;indice (i, j, k) avec le classement (classement[i], classement[j], classement[k]).<br \/>Une \u00e9quipe est valide si : (rating[i] &lt; rating[j] &lt; rating[k]) ou (rating[i] &gt; rating[j] &gt; rating[k]) o\u00f9 (0 &lt;= i &lt; j &lt; k &lt; n).<br \/>Renvoyez le nombre d&rsquo;\u00e9quipes que vous pouvez former compte tenu des conditions. (les soldats peuvent faire partie de plusieurs \u00e9quipes).<\/p><p>Exemple 1:<\/p><p>Entr\u00e9e : note = [2,5,3,4,1]<br \/>Sortie\u00a0: 3<br \/>Explication : On peut former trois \u00e9quipes compte tenu des conditions. (2,3,4), (5,4,1), (5,3,1).<\/p><p>Exemple 2\u00a0:<\/p><p>Entr\u00e9e : note = [2,1,3]<br \/>Sortie\u00a0: 0<br \/>Explication : Nous ne pouvons former aucune \u00e9quipe compte tenu des conditions.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ee098a3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ee098a3\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ba22174\" data-id=\"ba22174\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-69b6a45 elementor-widget elementor-widget-toggle\" data-id=\"69b6a45\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1101\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1101\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1101\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1101\"><p>Il est facile de faire un <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/algorithm-naif-greedy-enumeration-2\/\">algorithme glouton<\/a>. Ce dernier est en O(n^3) donc on va essayer d&rsquo;am\u00e9liorer la <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/complexity-in-time\/\">complexit\u00e9<\/a> avec de la programmation dynamique.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19358 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/nombreequipe.png\" alt=\"nombre \u00e9quipe programmation dynamique\" width=\"442\" height=\"481\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/nombreequipe.png 442w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/nombreequipe-276x300.png 276w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/nombreequipe-11x12.png 11w\" sizes=\"(max-width: 442px) 100vw, 442px\" \/><\/p><p>Voici l&rsquo;id\u00e9e principale dans la version programmation dynamique :<\/p><p>Premi\u00e8rement, nous calculons ce cas note[i] &gt; note[j] &gt; note[k] \u00e9tant donn\u00e9 que i &gt; j &gt; k. Ensuite, calculez le cas note[i] &lt; note[j] &lt; note[k].<\/p><p>D\u00e9finir dp[i]\u00a0: combien d&rsquo;\u00e9l\u00e9ments dans la notation de 0 \u00e0 i-1 sont inf\u00e9rieurs \u00e0 la notation[i].<\/p><p>Pour chaque fois que nous avons trouv\u00e9 note[i] &gt; note[j], nous accumulons dp[j]. Ici, dp[j] signifie combien de notes[k] existent de 0 \u00e0 j-1. C&rsquo;est-\u00e0-dire, combien de cas satisfont la note[i] &gt; la note[j] &gt; la note[k].<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19359 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/nombreequipe2.png\" alt=\"nombre \u00e9quipe programmation dynamique\" width=\"431\" height=\"703\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/nombreequipe2.png 431w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/nombreequipe2-184x300.png 184w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/nombreequipe2-7x12.png 7w\" sizes=\"(max-width: 431px) 100vw, 431px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8f2ce2f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8f2ce2f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0fa0525\" data-id=\"0fa0525\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f339a77 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"f339a77\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-875793a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"875793a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-df1c6d4\" data-id=\"df1c6d4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4c1868b elementor-widget elementor-widget-heading\" data-id=\"4c1868b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-10\"><\/span>Exercice 10<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-250c6f2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"250c6f2\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0556617\" data-id=\"0556617\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9440d9c elementor-widget elementor-widget-text-editor\" data-id=\"9440d9c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>On vous donne un tableau de prix o\u00f9 prix[i] est le prix d&rsquo;une action donn\u00e9e le i\u00e8me jour, et des frais entiers repr\u00e9sentant des frais de transaction.<\/p><p>Trouvez le profit maximum que vous pouvez r\u00e9aliser. Vous pouvez effectuer autant de transactions que vous le souhaitez, mais vous devez payer les frais de transaction pour chaque transaction.<\/p><p>Remarque\u00a0: Vous ne pouvez pas vous engager dans plusieurs transactions simultan\u00e9ment (c&rsquo;est-\u00e0-dire que vous devez vendre l&rsquo;action avant d&rsquo;acheter \u00e0 nouveau).<\/p><p>Entr\u00e9e : prix = [1,3,2,8,4,9], frais = 2<br \/>Sortie\u00a0: 8<\/p><p>Explication\u00a0: Le profit maximal peut \u00eatre atteint en\u00a0:<br \/>&#8211; Acheter \u00e0 des prix [0] = 1<br \/>&#8211; Vendre \u00e0 des prix[3] = 8<br \/>&#8211; Acheter \u00e0 des prix [4] = 4<br \/>&#8211; Vendre \u00e0 des prix[5] = 9<\/p><p>Le b\u00e9n\u00e9fice total est ((8 &#8211; 1) &#8211; 2) + ((9 &#8211; 4) &#8211; 2) = 8.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1279186 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1279186\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fb9d9e3\" data-id=\"fb9d9e3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-468676a elementor-widget elementor-widget-toggle\" data-id=\"468676a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-7391\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-7391\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-7391\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-7391\"><p>Commen\u00e7ons dans un premier temps avec l&rsquo;approche top-down.<\/p><ul><li>Soit dp(i, canBuy) le profit maximum que nous pouvons tirer des prix[i..n-1] avec le drapeau canBuy == True signifie que nous pouvons acheter le i\u00e8me jour.<\/li><li>Pour le i\u00e8me jour nous avons 2 options :<ul><li>Ignorez-le : profit = dp(i+1)<\/li><li>Achetez-le ou vendez-le<ul><li>Si achat : profit = dp(i+1) &#8211; prix[i]<\/li><li>Si vente : profit = dp(i+1) + prix[i] &#8211; commission<\/li><\/ul><\/li><\/ul><\/li><\/ul><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19373 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente.png\" alt=\"achat vente programmation dynamique\" width=\"476\" height=\"404\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente.png 476w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente-300x255.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente-14x12.png 14w\" sizes=\"(max-width: 476px) 100vw, 476px\" \/><\/p><p>On va convertir en une approche bottom-up pour faire de la programmation dynamique plus traditionnelle.<\/p><p>Soit dp[i][j] le profit maximum que nous pouvons tirer des prix[i..n-1] avec le drapeau j == 1 signifie que nous pouvons acheter le i\u00e8me jour.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19374 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente2.png\" alt=\"achat vente programmation dynamique\" width=\"572\" height=\"316\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente2.png 572w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente2-300x166.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente2-18x10.png 18w\" sizes=\"(max-width: 572px) 100vw, 572px\" \/><\/p><p>Puisque notre dp n&rsquo;acc\u00e8de qu&rsquo;\u00e0 2 \u00e9tats : l&rsquo;\u00e9tat dp actuel dp, l&rsquo;\u00e9tat dp pr\u00e9c\u00e9dent dpPrev. Nous pouvons optimiser \u00e0 O(1) dans la complexit\u00e9 de l&rsquo;espace.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19375 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente3.png\" alt=\"achat vente programmation dynamique\" width=\"535\" height=\"335\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente3.png 535w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente3-300x188.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/achatvente3-18x12.png 18w\" sizes=\"(max-width: 535px) 100vw, 535px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c474ad3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c474ad3\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fdac57f\" data-id=\"fdac57f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5f0be05 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"5f0be05\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fdc0b97 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fdc0b97\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7b21a5e\" data-id=\"7b21a5e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-43cd761 elementor-widget elementor-widget-heading\" data-id=\"43cd761\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-11\"><\/span>Exercice 11<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8e80003 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8e80003\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4362eb5\" data-id=\"4362eb5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bc9920b elementor-widget elementor-widget-text-editor\" data-id=\"bc9920b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Vous avez pr\u00e9vu un voyage en train un an \u00e0 l&rsquo;avance. Les jours de l&rsquo;ann\u00e9e au cours desquels vous voyagerez sont donn\u00e9s sous la forme d&rsquo;un nombre entier de jours. Chaque jour est un entier compris entre 1 et 365.<\/p><p>Les billets de train sont vendus de trois mani\u00e8res diff\u00e9rentes :<\/p><p>un pass 1 jour est vendu au prix de [0] dollars,<br \/>un laissez-passer de 7 jours est vendu pour des co\u00fbts [1] dollars, et<br \/>un laissez-passer de 30 jours est vendu pour des co\u00fbts [2] dollars.<br \/>Les laissez-passer permettent autant de jours de voyage cons\u00e9cutifs.<\/p><p>Par exemple, si nous obtenons un pass 7 jours le jour 2, nous pouvons voyager pendant 7 jours : 2, 3, 4, 5, 6, 7 et 8.<br \/>Renvoyez le nombre minimum de dollars dont vous avez besoin pour voyager chaque jour dans la liste de jours donn\u00e9e.<br \/>Entr\u00e9e : jours = [1,4,6,7,8,20], co\u00fbts = [2,7,15]<br \/>Sortie\u00a0: 11<\/p><p>Par exemple, voici une fa\u00e7on d&rsquo;acheter des laissez-passer qui vous permet de voyager selon votre plan de voyage\u00a0:<br \/>Le jour 1, vous avez achet\u00e9 un pass 1 jour pour un co\u00fbt[0] = 2 $, qui couvrait le jour 1.<br \/>Le jour 3, vous avez achet\u00e9 un pass de 7 jours pour un co\u00fbt[1] = 7 $, qui couvrait les jours 3, 4, &#8230;, 9.<br \/>Le jour 20, vous avez achet\u00e9 un pass d&rsquo;un jour pour un co\u00fbt[0] = 2 $, qui couvrait le jour 20.<\/p><p>Au total, vous avez d\u00e9pens\u00e9 11 $ et couvert tous les jours de votre voyage.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9b78c5b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9b78c5b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7d6b8ba\" data-id=\"7d6b8ba\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-33b2ac5 elementor-widget elementor-widget-toggle\" data-id=\"33b2ac5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5421\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5421\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5421\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5421\"><p>Nous allons voir ici l&rsquo;approche bottom-up car le raisonnement est tr\u00e8s similaire au probl\u00e8me de <a href=\"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/backpack-problem\/\">sac-\u00e0-dos<\/a> (knapsack) dans la construction de la solution.<\/p><p>dp[i] signifie jusqu&rsquo;au i\u00e8me jour le co\u00fbt minimum des billets. La taille du tableau dp d\u00e9pend du dernier jour de voyage, nous n&rsquo;avons donc pas besoin d&rsquo;une longueur de tableau de 365.<\/p><p>Nous avons besoin d&rsquo;un tableau bool\u00e9en pour marquer les jours de voyage, la raison en est que si ce n&rsquo;est pas un jour de voyage, nous n&rsquo;avons pas besoin de billet. Cependant, s&rsquo;il s&rsquo;agit d&rsquo;un jour de voyage, nous envisageons trois sc\u00e9narios (avec trois types de tickects)\u00a0:<\/p><p>Si un ticket 1 jour le jour i, dp[i] = dp[i &#8211; 1] + co\u00fbt[0]<br \/>Si un billet de 7 jours se termine le jour i, dp[i] = min(dp[i &#8211; 7], dp[i &#8211; 6] &#8230; dp[i &#8211; 1]) + co\u00fbt[1]<br \/>Si un ticket de 30 jours se termine le jour i, dp[i] = min(dp[i &#8211; 30], dp[i &#8211; 29] &#8230; dp[i &#8211; 1]) + co\u00fbt[2]<\/p><p>Mais puisque la valeur de dp array augmente, donc :<br \/>Pour un ticket 7 jours se terminant le jour i, dp[i] = dp[i &#8211; 7] + co\u00fbt[1]<br \/>Pour un ticket 30 jours se terminant le jour i, dp[i] = dp[i &#8211; 30] + co\u00fbt[2]<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19376 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/ticket.png\" alt=\"ticket programmation dynamique\" width=\"605\" height=\"480\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/ticket.png 605w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/ticket-300x238.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/ticket-15x12.png 15w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/ticket-600x476.png 600w\" sizes=\"(max-width: 605px) 100vw, 605px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-118954c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"118954c\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e569183\" data-id=\"e569183\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-36275c3 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"36275c3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a57d67f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a57d67f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-514fa96\" data-id=\"514fa96\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6f87750 elementor-widget elementor-widget-heading\" data-id=\"6f87750\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-12\"><\/span>Exercice 12<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4acb2ab elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4acb2ab\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7e99b27\" data-id=\"7e99b27\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6eec1f4 elementor-widget elementor-widget-text-editor\" data-id=\"6eec1f4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>On vous donne un tableau de valeurs enti\u00e8res o\u00f9 values[i] repr\u00e9sente la valeur du i\u00e8me site touristique. Deux sites touristiques i et j ont une distance j &#8211; i entre eux.<\/p><p>Le score d&rsquo;une paire (i &lt; j) de sites touristiques est valeurs[i] + valeurs[j] + i &#8211; j\u00a0: la somme des valeurs des sites touristiques, moins la distance qui les s\u00e9pare.<\/p><p>Renvoie le score maximum d&rsquo;une paire de sites touristiques.<\/p><p>Entr\u00e9e : valeurs = [8,1,5,2,6]<br \/>Sortie\u00a0: 11<\/p><p>Nous avons i = 0, j = 2, valeurs[i] + valeurs[j] + i &#8211; j = 8 + 5 + 0 &#8211; 2 = 11<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4af4d12 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4af4d12\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-27c1815\" data-id=\"27c1815\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4da47af elementor-widget elementor-widget-toggle\" data-id=\"4da47af\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-8141\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-8141\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-8141\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-8141\"><p>Supposons que nous choisissions le site [i,&#8230;j]. La partition peut \u00eatre d\u00e9compos\u00e9e en 2 parties.<\/p><p>La premi\u00e8re partie est le startGain que vous gagnez en commen\u00e7ant \u00e0 un certain point i. Notez que startGain[i] = a[i] + i.<\/p><p>La deuxi\u00e8me partie est le endGain qui est le montant que vous gagnez en terminant \u00e0 un certain point j. Notez que endGain[i] = a[j] &#8211; j.<\/p><p>Notez que endGain peut \u00eatre n\u00e9gatif.<\/p><p>Le gain global pour [i,&#8230;j] n&rsquo;est rien d&rsquo;autre que startGain[i] + endGain[j]. (Cela peut \u00eatre facilement v\u00e9rifi\u00e9 par les d\u00e9finitions).<\/p><p>Nous devons maximiser le gain global.<\/p><p>Quelles sont les positions possibles pour commencer le voyage ? Il est clair que nous pouvons tout commencer sauf le dernier \u00e9l\u00e9ment. Ainsi, le voyage optimal doit commencer \u00e0 l&rsquo;un de ces \u00e9l\u00e9ments.<\/p><p>Supposons que nous ne soyons autoris\u00e9s \u00e0 commencer un voyage qu&rsquo;\u00e0 i. Quel est le montant maximum que nous pouvons gagner dans ce cas ? Eh bien, puisque le startGain est fixe, nous devons maximiser le endGain. Nous pouvons le faire en nous arr\u00eatant \u00e0 un \u00e9l\u00e9ment qui a le maximum endGain \u00e0 condition qu&rsquo;il apparaisse \u00e0 droite de i.<\/p><p>Comme indiqu\u00e9 ci-dessus, pour chaque i, nous devons trouver le endGain maximal \u00e0 sa droite.<\/p><p>maxEndRight[i] = max(maxEndRight[i+1], endGain[i+1]) = max(maxEndRight[i+1], a[i+1] &#8211; (i+1))<\/p><p>maxEndRight[i] repr\u00e9sente le endGain le plus \u00e9lev\u00e9 que vous pouvez obtenir en vous arr\u00eatant \u00e0 n&rsquo;importe quel point strictement \u00e0 droite de i. Puisque par d\u00e9finition, nous connaissons d\u00e9j\u00e0 endGain[i+1] (le gain le plus \u00e9lev\u00e9 possible en terminant \u00e0 n&rsquo;importe quel point \u00e0 droite de i+1), nous n&rsquo;avons qu&rsquo;\u00e0 v\u00e9rifier la possibilit\u00e9 de savoir si s&rsquo;arr\u00eater \u00e0 i+1 serait b\u00e9n\u00e9fique ou non. D&rsquo;o\u00f9 la d\u00e9finition de DP.<\/p><p>Pour chaque i valide, overallGain[i] = startGain[i] + maxEndRight[i] = a[i] + i + maxEndRight[i]<\/p><p>Notez que maxEndRight[i] ne d\u00e9pend que de maxEndRight[i+1]. Par cons\u00e9quent, nous pouvons utiliser 2 variables pour suivre les valeurs pr\u00e9c\u00e9dentes.<\/p><p>Puisque nous avons besoin de la valeur de maxEndRight[i+1] pour calculer la valeur de maxEndRight[i], nous commen\u00e7ons donc les it\u00e9rations \u00e0 l&rsquo;arri\u00e8re.<\/p><p>Comme indiqu\u00e9, les voyages ne peuvent pas commencer au dernier \u00e9l\u00e9ment, donc la boucle for commence \u00e0 i=n-2. Pour cette valeur, maxEndingRight est initialis\u00e9 \u00e0 endGain[lastIndex] car c&rsquo;est le seul moyen possible de terminer le voyage.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19381 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/exploration.png\" alt=\"exploration programmation dynamique\" width=\"509\" height=\"455\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/exploration.png 509w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/exploration-300x268.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/exploration-13x12.png 13w\" sizes=\"(max-width: 509px) 100vw, 509px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-89c6b96 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"89c6b96\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-24d5180\" data-id=\"24d5180\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-98f903e elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"98f903e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c1f04d8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c1f04d8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d5c8044\" data-id=\"d5c8044\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-98822c5 elementor-widget elementor-widget-heading\" data-id=\"98822c5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-13\"><\/span>Exercice 13<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0ddfff5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0ddfff5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f0b6ad6\" data-id=\"f0b6ad6\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7b86837 elementor-widget elementor-widget-text-editor\" data-id=\"7b86837\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Vous \u00eates un voleur professionnel qui envisage de cambrioler des maisons le long d&rsquo;une rue. Chaque maison a une certaine somme d&rsquo;argent cach\u00e9e, la seule contrainte vous emp\u00eachant de cambrioler chacune d&rsquo;elles est que les maisons adjacentes ont des syst\u00e8mes de s\u00e9curit\u00e9 connect\u00e9s et elle contactera automatiquement la police si deux maisons adjacentes ont \u00e9t\u00e9 cambriol\u00e9es la m\u00eame nuit.<\/p><p>\u00c9tant donn\u00e9 un tableau d&rsquo;entiers nums repr\u00e9sentant le montant d&rsquo;argent de chaque maison, renvoyez le montant d&rsquo;argent maximum que vous pouvez voler ce soir sans alerter la police.<\/p><p>Entr\u00e9e : nombres = [1,2,3,1]<br \/>Sortie\u00a0: 4<br \/>Explication : Voler la maison 1 (argent = 1) puis voler la maison 3 (argent = 3).<br \/>Montant total que vous pouvez voler = 1 + 3 = 4.<\/p><p>Entr\u00e9e : nombres = [2,7,9,3,1]<br \/>Sortie\u00a0: 12<br \/>Explication : Voler la maison 1 (argent = 2), voler la maison 3 (argent = 9) et voler la maison 5 (argent = 1).<br \/>Montant total que vous pouvez voler = 2 + 9 + 1 = 12.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-16b7f12 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"16b7f12\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-6f8a9b0\" data-id=\"6f8a9b0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2faf767 elementor-widget elementor-widget-toggle\" data-id=\"2faf767\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5001\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5001\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5001\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5001\"><p>Trouvons une relation r\u00e9cursive.<\/p><p>Un voleur a 2 options : a) voler la maison actuelle i ; b) ne cambriolez pas la maison actuelle.<\/p><p>Si une option \u00ab\u00a0a\u00a0\u00bb est s\u00e9lectionn\u00e9e, cela signifie qu&rsquo;elle ne peut pas voler la maison i-1 pr\u00e9c\u00e9dente, mais peut passer en toute s\u00e9curit\u00e9 \u00e0 celle qui pr\u00e9c\u00e8de la i-2 pr\u00e9c\u00e9dente et obtient tout le butin cumulatif qui suit.<\/p><p>Si une option \u00ab\u00a0b\u00a0\u00bb est s\u00e9lectionn\u00e9e, le voleur obtient tout le butin possible du vol de i-1 et de tous les b\u00e2timents suivants.<\/p><p>Cela revient donc \u00e0 calculer ce qui est le plus rentable :<\/p><p>vol de la maison actuelle + pillage des maisons avant la pr\u00e9c\u00e9dente le butin du vol de maison pr\u00e9c\u00e9dent et tout butin captur\u00e9 avant cela<br \/>rob(i) = Math.max( rob(i &#8211; 2) + currentHouseValue, rob(i &#8211; 1) )<\/p><p>Cela donnerait la version r\u00e9cursive suivante :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19625 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob1.png\" alt=\"rob house recursive\" width=\"492\" height=\"212\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob1.png 492w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob1-300x129.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob1-18x8.png 18w\" sizes=\"(max-width: 492px) 100vw, 492px\" \/><\/p><p>R\u00e9fl\u00e9chissons maintenant \u00e0 une m\u00e9thode utilisant la m\u00e9mo\u00efsation. Pour cela, nous allons consid\u00e9rer qu&rsquo;\u00e0 l&rsquo;ajout de chaque maison (donc \u00e0 l&rsquo;\u00e9tape i, soit on ne vole pas cette maison (donc m\u00eame valeur que l&rsquo;\u00e9tape i-1), soit on vole la maison et donc potentiellement celle en i-2.<\/p><p>Nous prenons donc le maximum entre l&rsquo;optimum en l&rsquo;\u00e9tape i-1 et en i-2 + valeur de la nouvelle maison. Pour rappel, chaque \u00e9tape est optimal car r\u00e9soudre le probl\u00e8me avec sans la nouvelle maison est optimale par principe de sous-probl\u00e8me.<\/p><p>Ce qui donne :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19626 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob2.png\" alt=\"rob house memoization\" width=\"542\" height=\"430\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob2.png 542w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob2-300x238.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob2-15x12.png 15w\" sizes=\"(max-width: 542px) 100vw, 542px\" \/><\/p><p>On est ici sur une complexit\u00e9 en m\u00e9moire et en temps en O(n).<\/p><p>Transformons ce code est bottom-up, donc en programmation dynamique :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19627 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob3.png\" alt=\"rob house programmation dynamique\" width=\"417\" height=\"264\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob3.png 417w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob3-300x190.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob3-18x12.png 18w\" sizes=\"(max-width: 417px) 100vw, 417px\" \/><\/p><p>Notons que comme Fibonacci nous n&rsquo;avons pas besoin de garder l&rsquo;ensemble des valeurs pr\u00e9c\u00e9dentes car le sous-probl\u00e8me optimale en i-1 et i-2 ne change pas quelque soit la nouvelle maison. Notez que cette optimisation ne permettra pas de savoir quelles maisons ont \u00e9t\u00e9 choisies !<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19628 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob4.png\" alt=\"rob house programmation dynamique\" width=\"339\" height=\"292\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob4.png 339w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob4-300x258.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/rob4-14x12.png 14w\" sizes=\"(max-width: 339px) 100vw, 339px\" \/><\/p><p>La complexit\u00e9 en espace est O(1).<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-22f016f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"22f016f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fc3233b\" data-id=\"fc3233b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-09ca359 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"09ca359\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-61a671c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"61a671c\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5055a6a\" data-id=\"5055a6a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3cc17c4 elementor-widget elementor-widget-heading\" data-id=\"3cc17c4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-14\"><\/span>Exercice 14<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-af6442b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"af6442b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-dcb03e6\" data-id=\"dcb03e6\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4025756 elementor-widget elementor-widget-text-editor\" data-id=\"4025756\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>On vous donne k oeufs identiques et vous avez acc\u00e8s \u00e0 un b\u00e2timent de n \u00e9tages num\u00e9rot\u00e9s de 1 \u00e0 n.<\/p><p>Vous savez qu&rsquo;il existe un \u00e9tage f o\u00f9 0 &lt;= f &lt;= n tel que tout \u0153uf tomb\u00e9 \u00e0 un \u00e9tage sup\u00e9rieur \u00e0 f se cassera, et tout \u0153uf tomb\u00e9 \u00e0 ou en dessous de l&rsquo;\u00e9tage f ne se cassera pas.<\/p><p>\u00c0 chaque mouvement, vous pouvez prendre un \u0153uf non cass\u00e9 et le faire tomber de n&rsquo;importe quel \u00e9tage x (o\u00f9 1 &lt;= x &lt;= n). Si l&rsquo;\u0153uf se casse, vous ne pouvez plus l&rsquo;utiliser. Cependant, si l&rsquo;\u0153uf ne se casse pas, vous pouvez le r\u00e9utiliser lors de futurs mouvements.<\/p><p>Renvoie le nombre minimum de mouvements dont vous avez besoin pour d\u00e9terminer avec certitude quelle est la valeur de f.<\/p><p>Entr\u00e9e : k = 1, n = 2<br \/>Sortie : 2<\/p><p>D\u00e9posez l&rsquo;\u0153uf de l&rsquo;\u00e9tage 1. S&rsquo;il se casse, nous savons que f = 0.<\/p><p>Sinon, laissez tomber l&rsquo;\u0153uf de l&rsquo;\u00e9tage 2. S&rsquo;il se casse, nous savons que f = 1.<br \/>S&rsquo;il ne casse pas, alors nous savons f = 2.<\/p><p>Par cons\u00e9quent, nous avons besoin d&rsquo;au moins 2 mouvements pour d\u00e9terminer avec certitude quelle est la valeur de f.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6b300d7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6b300d7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-83fa393\" data-id=\"83fa393\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-de92cf1 elementor-widget elementor-widget-toggle\" data-id=\"de92cf1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2331\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2331\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2331\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2331\"><p>Tout d&rsquo;abord, nous pouvons voir que pour obtenir la r\u00e9ponse d&rsquo;\u00e9tages et d&rsquo;\u0153ufs plus grands, les r\u00e9sultats de cas plus petits sont utiles pour l&rsquo;analyse, ce qui conduit \u00e0 une programmation dynamique.<\/p><p>Ensuite, comment d\u00e9finir un \u00e9tat pour chaque l\u00e2ch\u00e9 afin d&rsquo;obtenir le plancher optimal ? Ici nous avons deux variables :<\/p><p>Le nombre d&rsquo;\u0153ufs restant \u00e0 jeter i, (0 &lt;= i &lt;= K)<br \/>Le nombre d&rsquo;\u00e9tages restant pour tester j, (1 &lt;= j &lt;= N)<\/p><p>La r\u00e9ponse (les plus petits temps pour obtenir le plancher optimal) peut \u00eatre la valeur de chaque \u00e9tat dp.<\/p><p>Le cas de base est plut\u00f4t intuitif \u00e0 trouver. Pensez aux cas avec des \u0153ufs et des planchers les plus petits :<\/p><p>dp[1][j] = j, j = 1&#8230;N # un \u0153uf, v\u00e9rifiez chaque \u00e9tage de 1 \u00e0 j<br \/>dp[i][0] = 0, i = 1&#8230;K # pas de plancher, pas de chute n\u00e9cessaire pour obtenir le plancher optimal<br \/>dp[i][1] = 1, i = 1&#8230;K # un \u00e9tage, v\u00e9rifier une seule fois<\/p><p>Pour obtenir une relation r\u00e9cursive, consid\u00e9rons un cas de test\u00a0: 3 \u0153ufs et 100 \u00e9tages.<\/p><p>Pour le prochaine l\u00e2ch\u00e9, je peux choisir un \u00e9tage de 1 \u00e0 100, disons que je choisis 25.<\/p><p>Il y a 2 r\u00e9sultats possibles pour ce l\u00e2ch\u00e9 :<\/p><p>l&rsquo;\u0153uf s&rsquo;est cass\u00e9, j&rsquo;ai maintenant 2 \u0153ufs, et le plancher \u00e0 choisir devient 1~24.<br \/>l&rsquo;oeuf reste en s\u00e9curit\u00e9, j&rsquo;ai encore 3 oeufs, et le plancher \u00e0 choisir devient 26~100.<\/p><p>Pensez au sc\u00e9nario du pire cas et utilisez la d\u00e9finition dp ci-dessus, nous pouvons d\u00e9crire la situation d&rsquo;obtention du plancher optimal en choisissant le plancher 25 pour la prochaine l\u00e2ch\u00e9 comme :<\/p><p>dp[3][100] = 1 + max(dp[2][24], dp[3][75])<\/p><p>Outre l&rsquo;\u00e9tage 25, en terme de prochain l\u00e2ch\u00e9 , nous pouvons \u00e9galement choisir l&rsquo;\u00e9tage de 1 \u00e0 100.<\/p><p>Chaque l\u00e2ch\u00e9 serait similaire au cas du 25 ci-dessus. Le r\u00e9sultat final serait le minimum de tous les choix possibles d&rsquo;\u00e9tages suivants \u00e0 d\u00e9poser :<\/p><p>dp[3][100] = min(&#8230;, 1 + max(dp[2][23], dp[3][76]), 1 + max(dp[2][24], dp[3][75]), 1 + max(dp[2][25], dp[3][74]), \u2026) (prenons l&rsquo;\u00e9tage 24, 25, 26 comme exemple)<\/p><p>Pour g\u00e9n\u00e9raliser l&rsquo;exemple ci-dessus, la formule dp serait\u00a0:<\/p><p>dp[i][j] = min(1 + max(dp[i-1][k-1], dp[i][j-k])), k = 1,2,&#8230;j<\/p><p>Par cons\u00e9quent, nous d\u00e9finissons dp[i][j] comme le plus petit nombre de gouttes pour obtenir le plancher optimal avec i \u0153ufs et j planchers restants.<\/p><p>Voici une premi\u00e8re solution en force brute en O(kn^2)<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19629 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/eggdrop1.png\" alt=\"egg drop force brute\" width=\"589\" height=\"458\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/eggdrop1.png 589w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/eggdrop1-300x233.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/eggdrop1-15x12.png 15w\" sizes=\"(max-width: 589px) 100vw, 589px\" \/><\/p><p>Cependant, cette id\u00e9e est tr\u00e8s brute force, car vous v\u00e9rifiez toutes les possibilit\u00e9s.<\/p><p>Je consid\u00e8re donc ce probl\u00e8me d&rsquo;une mani\u00e8re diff\u00e9rente:<br \/>dp[M][K]signifie que, \u00e9tant donn\u00e9 K oeufs et M coups,\u00a0quel est le nombre maximum d&rsquo;\u00e9tages que nous pouvons v\u00e9rifier.<\/p><p>L&rsquo;\u00e9quation dp est :\u00a0dp[m][k] = dp[m &#8211; 1][k &#8211; 1] + dp[m &#8211; 1][k] + 1,<br \/>ce qui signifie que nous prenons 1 mouvement vers un \u00e9tage,\u00a0si l&rsquo;\u0153uf se casse, alors nous pouvons v\u00e9rifier dp[m &#8211; 1][k &#8211; 1] \u00e9tages.\u00a0si l&rsquo;\u0153uf ne se casse pas, alors nous pouvons v\u00e9rifier dp[m &#8211; 1][k] \u00e9tages.<\/p><p>Ce qui donnerai le code suivant :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19630 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/eggdrop2.png\" alt=\"egg drop programmation dynamique\" width=\"446\" height=\"153\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/eggdrop2.png 446w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/eggdrop2-300x103.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/eggdrop2-18x6.png 18w\" sizes=\"(max-width: 446px) 100vw, 446px\" \/><\/p><p>Ne tenter pas ce code, vous aurez un TLE ! Il faudrait l&rsquo;optimiser avec un Binary Tree que l&rsquo;on fera dans un autre cours !<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4192d37 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4192d37\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3b19697\" data-id=\"3b19697\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d4130d3 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"d4130d3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ebf5b84 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ebf5b84\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c224686\" data-id=\"c224686\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0f82cba elementor-widget elementor-widget-heading\" data-id=\"0f82cba\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-15\"><\/span>Exercice 15<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6313870 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6313870\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7185a7f\" data-id=\"7185a7f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5f2b49c elementor-widget elementor-widget-text-editor\" data-id=\"5f2b49c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Les d\u00e9mons ont captur\u00e9 la princesse et l&rsquo;ont emprisonn\u00e9e dans le coin inf\u00e9rieur droit d&rsquo;un donjon. Le donjon se compose de m x n pi\u00e8ces dispos\u00e9es dans une grille 2D. Notre vaillant chevalier est initialement positionn\u00e9 dans la salle en haut \u00e0 gauche et doit se frayer un chemin \u00e0 travers le donjon pour sauver la princesse.<\/p><p>Le chevalier a un nombre de points de vie initial repr\u00e9sent\u00e9 par un entier positif. Si \u00e0 tout moment ses points de vie tombe \u00e0 0 ou en dessous, il meurt imm\u00e9diatement.<\/p><p>Certaines pi\u00e8ces sont gard\u00e9es par des d\u00e9mons (repr\u00e9sent\u00e9s par des nombres entiers n\u00e9gatifs), de sorte que le chevalier perd de la sant\u00e9 en entrant dans ces pi\u00e8ces\u00a0; les autres salles sont soit vides (repr\u00e9sent\u00e9es par 0), soit contiennent des orbes magiques qui augmentent la sant\u00e9 du chevalier (repr\u00e9sent\u00e9es par des nombres entiers positifs).<\/p><p>Pour atteindre la princesse le plus rapidement possible, le chevalier d\u00e9cide de se d\u00e9placer uniquement vers la droite ou vers le bas \u00e0 chaque pas.<\/p><p>Donner la sant\u00e9 initiale minimale du chevalier afin qu&rsquo;il puisse sauver la princesse.<\/p><p>Notez que n&rsquo;importe quelle pi\u00e8ce peut contenir des menaces ou des power-ups, m\u00eame la premi\u00e8re pi\u00e8ce dans laquelle le chevalier entre et la pi\u00e8ce en bas \u00e0 droite o\u00f9 la princesse est emprisonn\u00e9e.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-19631\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/dungeon-grid-1.jpg\" alt=\"donjon programmation dynamique\" width=\"253\" height=\"253\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/dungeon-grid-1.jpg 253w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/dungeon-grid-1-150x150.jpg 150w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/dungeon-grid-1-12x12.jpg 12w\" sizes=\"(max-width: 253px) 100vw, 253px\" \/><\/p><p>Entr\u00e9e : donjon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]<br \/>Sortie\u00a0: 7<br \/>Explication : La sant\u00e9 initiale du chevalier doit \u00eatre d&rsquo;au moins 7 s&rsquo;il suit le chemin optimal : DROITE-&gt; DROITE -&gt; BAS -&gt; BAS.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-44f7431 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"44f7431\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8bc1551\" data-id=\"8bc1551\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a2cb582 elementor-widget elementor-widget-toggle\" data-id=\"a2cb582\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1701\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1701\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1701\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1701\"><p>Probablement lorsque vous voyez ce probl\u00e8me et que vous avez une certaine exp\u00e9rience dans ce type de probl\u00e8mes, vous pouvez deviner qu&rsquo;il s&rsquo;agit d&rsquo;un probl\u00e8me de programmation dynamique. Cependant, m\u00eame si vous comprenez cela, il n&rsquo;est pas facile de le r\u00e9soudre. Utilisons dp de haut en bas, c&rsquo;est-\u00e0-dire Soit dp[i][j] le hp minimum dont nous avons besoin pour atteindre la princesse si nous partons du point (i,j). Consid\u00e9rons l&rsquo;exemple suivant :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-19632\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon2.png\" alt=\"donjon programmation dynamique\" width=\"218\" height=\"186\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon2.png 218w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon2-14x12.png 14w\" sizes=\"(max-width: 218px) 100vw, 218px\" \/><\/p><p>Ajoutons une ligne factice en bas et une colonne factice \u00e0 droite pour g\u00e9rer plus facilement les cas de bordure. Nous le remplissons d&rsquo;infinis, sauf deux &#8211; voisins de notre princesse. Je l&rsquo;expliquerai un peu plus tard.<\/p><p>Comment \u00e9valuer dp[i][j] ? Nous devons examiner deux cellules\u00a0: dp[i+1][j] et dp[i][j+1] et \u00e9valuer deux candidats possibles\u00a0: dp[i+1][j]-donjon[i][j] et dp[i][j+1]-donjon[i][j].<\/p><ol><li>Si au moins un de ces deux nombres est n\u00e9gatif, cela signifie que l&rsquo;on peut survivre avec juste 1 hp : (regardez le nombre +30 dans notre tableau par exemple)<\/li><li>Si ces deux nombres sont positifs, il faut en prendre le minimum, voir par exemple le nombre -10 dans notre tableau : pour survivre il faut soit 5- -10 = 15 si on va \u00e0 droite et 1- -10 = 11 si on descend, bien s\u00fbr on choisit 11.<\/li><\/ol><p>Ces conditions peuvent \u00eatre \u00e9crites sur une \u00e9quation : dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-donjon[i][j],1).<\/p><p>Enfin, pourquoi j&rsquo;ai mis 1 \u00e0 2 voisins de princesse ? Pour rendre cette formule valable pour la cellule princesse : si nous avons un nombre n\u00e9gatif comme -5 dans cette cellule, nous avons besoin de 6 gp pour survivre, si nous avons un nombre non n\u00e9gatif dans cette cellule, nous avons besoin de 1 gp pour survivre.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19633 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon3.png\" alt=\"donjon programmation dynamique\" width=\"238\" height=\"244\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon3.png 238w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon3-12x12.png 12w\" sizes=\"(max-width: 238px) 100vw, 238px\" \/><\/p><p>La complexit\u00e9 en temps et espace est de O(nm)<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19634 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon4.png\" alt=\"donjon programmation dynamique\" width=\"546\" height=\"267\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon4.png 546w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon4-300x147.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/donjon4-18x9.png 18w\" sizes=\"(max-width: 546px) 100vw, 546px\" \/><\/p><p>Il est \u00e9galement possible de le faire avec dp descendant, mais dans ce cas, vous devez utiliser la recherche binaire, car vous ne savez pas \u00e0 l&rsquo;avance si vous survivez \u00e0 partir de x HP ou non. La complexit\u00e9 sera O(nm log(MAX_HP)) dans ce cas.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fd72c7b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fd72c7b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0479022\" data-id=\"0479022\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-67ff1a5 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"67ff1a5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-39da0fa elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"39da0fa\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f01fbb7\" data-id=\"f01fbb7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1cb9924 elementor-widget elementor-widget-heading\" data-id=\"1cb9924\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-16\"><\/span>Exercice 16<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ac42efa elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ac42efa\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-57ebef3\" data-id=\"57ebef3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-81c0ba2 elementor-widget elementor-widget-text-editor\" data-id=\"81c0ba2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>On vous donne une grille matricielle lignes x cols repr\u00e9sentant un champ de cerises o\u00f9 grid[i][j] repr\u00e9sente le nombre de cerises que vous pouvez collecter \u00e0 partir de la cellule (i, j).<\/p><p>Vous avez deux robots qui peuvent ramasser des cerises pour vous :<\/p><p>Le robot #1 est situ\u00e9 dans le coin sup\u00e9rieur gauche (0, 0) et<br \/>Le robot #2 est situ\u00e9 dans le coin sup\u00e9rieur droit (0, cols &#8211; 1).<\/p><p>Renvoyez le nombre maximum de collecte de cerises \u00e0 l&rsquo;aide des deux robots en suivant les r\u00e8gles ci-dessous :<\/p><p>\u00c0 partir d&rsquo;une cellule (i, j), les robots peuvent se d\u00e9placer vers la cellule (i + 1, j &#8211; 1), (i + 1, j) ou (i + 1, j + 1).<br \/>Lorsqu&rsquo;un robot traverse une cellule, il ramasse toutes les cerises et la cellule devient une cellule vide.<br \/>Lorsque les deux robots restent dans la m\u00eame cellule, un seul prend les cerises.<br \/>Les deux robots ne peuvent \u00e0 aucun moment sortir de la grille.<br \/>Les deux robots doivent atteindre la rang\u00e9e inf\u00e9rieure de la grille.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-19638\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup1-300x271.png\" alt=\"pickup programmation dynamique\" width=\"300\" height=\"271\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup1-300x271.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup1-13x12.png 13w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup1.png 568w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>Entr\u00e9e : grille = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]<br \/>Sortie\u00a0: 28<\/p><p>Explication\u00a0: Les trajectoires des robots\u00a01 et\u00a02 sont respectivement d\u00e9crites en vert et en bleu.<br \/>Cerises prises par Robot #1, (1 + 9 + 5 + 2) = 17.<br \/>Cerises prises par Robot #2, (1 + 3 + 4 + 3) = 11.<br \/>Total de cerises : 17 + 11 = 28.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-77538ff elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"77538ff\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0f3d539\" data-id=\"0f3d539\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7fa729f elementor-widget elementor-widget-toggle\" data-id=\"7fa729f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1331\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1331\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1331\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1331\"><p>Dans ce probl\u00e8me, nous supposerons que les deux robots passeront \u00e0 la rang\u00e9e suivante en m\u00eame temps afin qu&rsquo;ils restent tous les deux dans la m\u00eame rang\u00e9e. Ce sera le premier aper\u00e7u pour r\u00e9soudre ce probl\u00e8me.<\/p><p>Comme d\u00e9crit dans l&rsquo;\u00e9nonc\u00e9 du probl\u00e8me, nous pouvons nous d\u00e9placer dans 3 directions (i+1, j-1) , (i+1, j) ou (i+1, j+1). Tous dans la ligne suivante mais avec une colonne diff\u00e9rente.<\/p><p>Puisque nous avons 3 directions pour chaque robot, il y a donc \u00e0 chaque rang\u00e9e 9 (3 x 3) \u00e9tats vers lesquels nous pouvons nous d\u00e9placer. (3 \u00e9tats pour le premier robot et 3 \u00e9tats pour le deuxi\u00e8me robot donc c&rsquo;est 3 x 3).<\/p><p>Et comme l&rsquo;indique l&rsquo;indice, nous devons avoir un tableau DP de 4 lignes. Comme il s&rsquo;agit d&rsquo;un tableau \u00e0 3 dimensions, il y aura un tableau \u00e0 2 dimensions qui sera n * n, c&rsquo;est-\u00e0-dire no. de colonne * no. de colonne. O\u00f9 la ligne sera d\u00e9finie par la position de la colonne Robot1 et la colonne pr\u00e9cisera la position de la colonne Robot2.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19640 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup2.png\" alt=\"pickup programmation dynamique\" width=\"1000\" height=\"446\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup2.png 1000w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup2-300x134.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup2-768x343.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup2-18x8.png 18w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" \/><\/p><p>Au d\u00e9part, nous savons que robot1 est \u00e0 la position 0 et que robot2 est \u00e0 la position colonne &#8211; 1, c&rsquo;est-\u00e0-dire la derni\u00e8re colonne.<\/p><p>Nous devons remplir dp[0] c&rsquo;est-\u00e0-dire la 1\u00e8re ligne et dans cette 1\u00e8re ligne, la position de colonne pour le robot sera (0, 2) car 0 signifie la position de colonne pour robot1 et 2 signifie la position de colonne pour robot2 dans la grille.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19641 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup3.png\" alt=\"programmation dynamique pickup\" width=\"1000\" height=\"423\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup3.png 1000w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup3-300x127.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup3-768x325.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup3-18x8.png 18w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" \/><\/p><p>Lorsque nous remplissons l&rsquo;espace, nous obtenons la valeur 3 + 1 soit 4<\/p><p>Maintenant, nous devons remplir la 2\u00e8me rang\u00e9e. Et dans la 2\u00e8me ligne \u00e9galement, il y aura une matrice n * m. Si nous prenons la position pr\u00e9c\u00e9dente de robot1 comme \u00e9tant 0, nous avons 3 colonnes dans lesquelles il peut aller dans la ligne suivante, c&rsquo;est-\u00e0-dire col {-1, 0, 1}. Comme col1 est hors limite, nous rejetons ce \u00ab\u00a0-1\u00a0\u00bb et ne gardons que \u00ab\u00a00, 1\u00a0\u00bb<\/p><p>Et pareil le robot2 est en 2, on peut soit atteindre la col {1, 2, 3}. Comme col3 est hors limite, nous le rejetons \u00ab\u00a03\u00a0\u00bb et ne gardons que \u00ab\u00a01, 2\u00a0\u00bb<\/p><p>Maintenant, lorsque nous cr\u00e9ons la combinaison de toutes les colonnes que robot1 et robot2 peuvent \u00eatre, nous obtenons 4 valeurs et lorsque nous la remplissons, ce sera\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19642 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup4.png\" alt=\"pickup programmation dynamique\" width=\"1000\" height=\"507\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup4.png 1000w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup4-300x152.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup4-768x389.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup4-18x9.png 18w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" \/><\/p><p>Donc, si nous regardons pour (0, 1) la valeur qui revient sera grid[0][1] + grid[1][1] + prev. Mais pour (1,1) ce sera grid[1][1] + prev.<\/p><p>Si on parle maintenant de code. Prenons dp[row][column][column] notre programmation dynamique. Au d\u00e9but col1=0 et col2=column-1 (emplacement des robots).<\/p><p>Nous avons la solution max=dp[0][col1][col2].<\/p><p>Voici le code permettant de remplir pour chaque valeur croissante de dp[raw][][]<\/p><pre><code class=\"language-cpp\"><span class=\"token\">\/\/ now comes a part where we need to iterate over each row;<\/span>\n        <span class=\"token\">for<\/span><span class=\"token\">(<\/span><span class=\"token\">int<\/span> i <span class=\"token\">=<\/span> <span class=\"token\">1<\/span><span class=\"token\">;<\/span> i <span class=\"token\">&lt;<\/span> row<span class=\"token\">;<\/span> i<span class=\"token\">++<\/span><span class=\"token\">)<\/span><span class=\"token\">{<\/span> <span class=\"token\">\/\/ each row starting with 1<\/span>\n            <span class=\"token\">\/\/ In this each row of dp, we need to excise our logic picking that particular column, as the starting position<\/span>\n            <span class=\"token\">\/\/ we need to loop on all the columns precise in this row<\/span>\n            <span class=\"token\">\/\/ as i told there will be n * m column<\/span>\n            <span class=\"token\">for<\/span><span class=\"token\">(<\/span><span class=\"token\">int<\/span> c1 <span class=\"token\">=<\/span> <span class=\"token\">0<\/span><span class=\"token\">;<\/span> c1 <span class=\"token\">&lt;<\/span> col<span class=\"token\">;<\/span> c1<span class=\"token\">++<\/span><span class=\"token\">)<\/span><span class=\"token\">{<\/span> \n                <span class=\"token\">for<\/span><span class=\"token\">(<\/span><span class=\"token\">int<\/span> c2 <span class=\"token\">=<\/span> <span class=\"token\">0<\/span><span class=\"token\">;<\/span> c2 <span class=\"token\">&lt;<\/span> col<span class=\"token\">;<\/span> c2<span class=\"token\">++<\/span><span class=\"token\">)<\/span><span class=\"token\">{<\/span>\n                    <span class=\"token\">\/\/ now from every column we need to fill the cube; for all the combinations or all the cell we can reach; with respective robot1 &amp; robot2<\/span>\n                    <span class=\"token\">\/\/ now we need to 1st take the previous value, that we disucssed<\/span>\n                    <span class=\"token\">int<\/span> prev <span class=\"token\">=<\/span> dp<span class=\"token\">[<\/span>i <span class=\"token\">-<\/span> <span class=\"token\">1<\/span><span class=\"token\">]<\/span><span class=\"token\">[<\/span>c1<span class=\"token\">]<\/span><span class=\"token\">[<\/span>c2<span class=\"token\">]<\/span><span class=\"token\">;<\/span> \n                    <span class=\"token\">if<\/span><span class=\"token\">(<\/span>prev <span class=\"token\">&gt;=<\/span> <span class=\"token\">0<\/span><span class=\"token\">)<\/span><span class=\"token\">{<\/span> <span class=\"token\">\/\/ if that the case, we need to perform our operation, if it is a -ve value it means that we haven't reach yet that particular cell. And above that's why we intialize the whole array with -1<\/span>\n                        <span class=\"token\">\/\/ Now we need to iterate over all the combinations of column that c1 &amp; c2 can be in. For that we had define a direction array at the top<\/span>\n                        <span class=\"token\">for<\/span><span class=\"token\">(<\/span><span class=\"token\">int<\/span> d1<span class=\"token\">:<\/span> dir<span class=\"token\">)<\/span><span class=\"token\">{<\/span> <span class=\"token\">\/\/ for c1 we have the direction \"d1\" and we iterate over it<\/span>\n                            col1 <span class=\"token\">=<\/span> d1 <span class=\"token\">+<\/span> c1<span class=\"token\">;<\/span> <span class=\"token\">\/\/ and column1 will be d1 + c1<\/span>\n                            <span class=\"token\">for<\/span><span class=\"token\">(<\/span><span class=\"token\">int<\/span> d2<span class=\"token\">:<\/span> dir<span class=\"token\">)<\/span><span class=\"token\">{<\/span> <span class=\"token\">\/\/ for c2 we have the direction \"d2\" and we iterate over it<\/span>\n                                col2 <span class=\"token\">=<\/span> d2 <span class=\"token\">+<\/span> c2<span class=\"token\">;<\/span> <span class=\"token\">\/\/ and column2 will be d2 + c2<\/span>\n                            <span class=\"token\">\/\/ Now we need to check is the new col1 &amp; col2 are in the range of 0 &amp; col. And for that we need to create a new method, which will check is the new col1 &amp; col2 are in the range<\/span>\n                                <span class=\"token\">if<\/span><span class=\"token\">(<\/span><span class=\"token\">inRange<\/span><span class=\"token\">(<\/span>col1<span class=\"token\">,<\/span> col<span class=\"token\">)<\/span> <span class=\"token\">&amp;&amp;<\/span> <span class=\"token\">inRange<\/span><span class=\"token\">(<\/span>col2<span class=\"token\">,<\/span> col<span class=\"token\">)<\/span><span class=\"token\">)<\/span><span class=\"token\">{<\/span>\n                                    dp<span class=\"token\">[<\/span>i<span class=\"token\">]<\/span><span class=\"token\">[<\/span>col1<span class=\"token\">]<\/span><span class=\"token\">[<\/span>col2<span class=\"token\">]<\/span> <span class=\"token\">=<\/span> Math<span class=\"token\">.<\/span><span class=\"token\">max<\/span><span class=\"token\">(<\/span>dp<span class=\"token\">[<\/span>i<span class=\"token\">]<\/span><span class=\"token\">[<\/span>col1<span class=\"token\">]<\/span><span class=\"token\">[<\/span>col2<span class=\"token\">]<\/span><span class=\"token\">,<\/span> prev<span class=\"token\">+<\/span><span class=\"token\">(<\/span>col1 <span class=\"token\">==<\/span> col2 <span class=\"token\">?<\/span> grid<span class=\"token\">[<\/span>i<span class=\"token\">]<\/span><span class=\"token\">[<\/span>col1<span class=\"token\">]<\/span> <span class=\"token\">:<\/span> <span class=\"token\">(<\/span>grid<span class=\"token\">[<\/span>i<span class=\"token\">]<\/span><span class=\"token\">[<\/span>col1<span class=\"token\">]<\/span> <span class=\"token\">+<\/span> grid<span class=\"token\">[<\/span>i<span class=\"token\">]<\/span><span class=\"token\">[<\/span>col2<span class=\"token\">]<\/span><span class=\"token\">)<\/span><span class=\"token\">)<\/span><span class=\"token\">)<\/span><span class=\"token\">;<\/span> <span class=\"token\">\/\/ if the value are int this range, we need to update the col1 &amp; col2 position in the i'th row<\/span>\n                                    max <span class=\"token\">=<\/span> Math<span class=\"token\">.<\/span><span class=\"token\">max<\/span><span class=\"token\">(<\/span>max<span class=\"token\">,<\/span> dp<span class=\"token\">[<\/span>i<span class=\"token\">]<\/span><span class=\"token\">[<\/span>col1<span class=\"token\">]<\/span><span class=\"token\">[<\/span>col2<span class=\"token\">]<\/span><span class=\"token\">)<\/span><span class=\"token\">;<\/span> <span class=\"token\">\/\/ we need to update the maximum at each step. Taking max of max value &amp; also the new column that we have filled<\/span>\n                                <span class=\"token\">}<\/span>\n                            <span class=\"token\">}<\/span>\n                        <span class=\"token\">}<\/span>\n                    <span class=\"token\">}<\/span>\n                    \n                <span class=\"token\">}<\/span>\n            <span class=\"token\">}<\/span>\n        <span class=\"token\">}<\/span>\n        <span class=\"token\">return<\/span> max<span class=\"token\">;<\/span> <span class=\"token\">\/\/eturn max at the end<\/span><\/code><\/pre><p>Appelons dp&rsquo; l&rsquo;approche montante. Voici un code mieux optimis\u00e9 en utilisant une approche descendante du probl\u00e8me d&rsquo;origine.<\/p><p>dp[k][i][j] indique si les deux robots partent de grid[k][i] et grid[k][j] le nombre total maximum de cerises qu&rsquo;ils peuvent enfin ramasser. Notez qu&rsquo;ils ne peuvent se d\u00e9placer qu&rsquo;en bas.<\/p><p>Apr\u00e8s avoir rempli dp, la r\u00e9ponse finale est dp[0][0][COL_NUM &#8211; 1]<\/p><p>Pour la derni\u00e8re ligne de grille, on a dp[-1][i][j] = grille[-1][i] si i == j sinon grille[-1][i] + grille[-1][j]. Notez que si 2 robots restent au m\u00eame endroit, ils ne peuvent ramasser qu&rsquo;une seule fois.<\/p><p>Pour les autres rang\u00e9es, nous devons parcourir toutes les combinaisons de directions 3 * 3 qu&rsquo;ils peuvent choisir dans la couche suivante et trouver le maximum, car pour chaque robot, il y a 3 directions dans lesquelles ils peuvent se d\u00e9placer.\u00a0<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19644 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup6.png\" alt=\"pickup programmation dynamique\" width=\"1000\" height=\"732\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup6.png 1000w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup6-300x220.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup6-768x562.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup6-16x12.png 16w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" \/><\/p><p>On aura donc le code suivant :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19645 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup7.png\" alt=\"pickup programmation dynamique\" width=\"740\" height=\"552\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup7.png 740w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup7-300x224.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup7-16x12.png 16w\" sizes=\"(max-width: 740px) 100vw, 740px\" \/><\/p><p>Ce n&rsquo;est pas tr\u00e8s optimal. Voici un code mieux optimis\u00e9 en python (en 2D avec une approche DFS) :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19643 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup5.png\" alt=\"pickup programmation dynamique\" width=\"490\" height=\"266\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup5.png 490w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup5-300x163.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/pickup5-18x10.png 18w\" sizes=\"(max-width: 490px) 100vw, 490px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Algorithmics Wiki Home Page Corrected exercises on dynamic programming This page offers several corrected exercises in dynamic programming and divide and conquer. The objective is \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":1062,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-15126","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15126","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=15126"}],"version-history":[{"count":27,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15126\/revisions"}],"predecessor-version":[{"id":20240,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15126\/revisions\/20240"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=15126"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}