{"topic":{"id":7272,"title":"oi-wiki DP 数字三角形疑问","slug":"topic","userId":1047,"categoryId":4,"createdAt":"2023-11-15 15:21:48.557402","bumpedAt":"2023-11-16 02:41:30.65978","views":240,"postsCount":3,"highestPostNumber":3,"likeCount":4,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":"看 OI-wiki 的 DP，有个疑问：这里为什么“每一步决策都是最优的”。我觉得换其他数字举例，可能会有最优的路径的中间步骤是局部最优的","deletedAt":null,"isAnonymous":false,"isPrivate":false,"isMembersOnly":false,"category":{"id":4,"name":"谈笑风生","slug":"general","color":"25AAE2"},"author":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif"},"realAuthor":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif"},"tags":[]},"posts":[{"id":17194,"postNumber":1,"raw":"看 OI-wiki 的 DP，有个疑问：\r\n![Screenshot|690x408](/uploads/image/8e/98/8e985adbbf12990a4a525fa12835a05af8b8cc688a091ca786144402740fa965.avif)\r\n这里为什么“每一步决策都是最优的”。我觉得换其他数字举例，可能会有最优的路径的中间步骤是局部最优的","cooked":"

看 OI-wiki 的 DP，有个疑问：
\n $\"Screenshot\"$
\n这里为什么“每一步决策都是最优的”。我觉得换其他数字举例，可能会有最优的路径的中间步骤是局部最优的

\n","createdAt":"2023-11-15 15:21:48.652051","updatedAt":"2023-11-15 15:21:48.652051","replyToPostNumber":null,"replyCount":0,"likeCount":2,"wordCount":58,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":2,"users":[{"id":307,"username":"Fast","name":null},{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":17203,"postNumber":2,"raw":"这个和 graph 中的最短路径一样。假如说从第 1 行的 7 到第 4 行的 7 的 7-3-8-7 不是最优路径，就说明从第 1 行的 7 到第 4 行的 7 有另一条路，其数字加起来是比 7-3-8-7 更大的。如果存在这条路，那么说明 7-3-8-7-5 就不是最优的，与假设前提矛盾。","cooked":"

这个和 graph 中的最短路径一样。假如说从第 1 行的 7 到第 4 行的 7 的 7-3-8-7 不是最优路径，就说明从第 1 行的 7 到第 4 行的 7 有另一条路，其数字加起来是比 7-3-8-7 更大的。如果存在这条路，那么说明 7-3-8-7-5 就不是最优的，与假设前提矛盾。

\n","createdAt":"2023-11-15 16:12:11.628095","updatedAt":"2024-10-25 11:18:53.730411","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":99,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":17219,"postNumber":3,"raw":"就是动态规划里的最优化原理。\n在此例中第一行到第五行的最优路径就等于\n第一行到第四行的第 i 个数字的最优路径加它到左下方或右下方（哪个大去哪）\n再对 i=1，2，3，4 的总路径长度取 max。\n所以这里的 7-3-8-7 指的不是第一行到第四行的最优路径\n而是第一行到第四行的第二个数字也就是 7 的最优路径。","cooked":"

就是动态规划里的最优化原理。
\n在此例中第一行到第五行的最优路径就等于
\n第一行到第四行的第 i 个数字的最优路径加它到左下方或右下方（哪个大去哪）
\n再对 i=1，2，3，4 的总路径长度取 max。
\n所以这里的 7-3-8-7 指的不是第一行到第四行的最优路径
\n而是第一行到第四行的第二个数字也就是 7 的最优路径。

\n","createdAt":"2023-11-16 02:41:30.65978","updatedAt":"2023-11-16 02:41:30.65978","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":126,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1457,"username":"cjc","name":"cjc","avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}}],"hasMore":false,"lastReadPostNumber":3,"hasUrlPostNumber":true}