Norwich (o◕∀◕)ﾉ°°Dynamic programming classic problems (Beginner-friendly and diverse)

ヾ(o◕∀◕)ﾉヾ各种动态规划经典例题（新手向、多类型）

一、前言

ν(･ω･`｡)我最近收集了几道比较常见的动态规划题目中的经典例题，并且特别适合新手作为学习入门的题目。这些题目可以帮助我们更好地理解各种不同的动态规划算法，并且很多题目也可以作为解题模板参考。内容量比较大哦~ 可以先三连 bookmark 然后慢慢研究哦（≧◡≦）如果哪里没有讲清楚或者大神看出哪里有问题的话麻烦多多提供建议蟹蟹~

二、线性dp

在线性动态规划问题中通常较为简便地确定状态转移方程；从逻辑上来说也比较清晰地分析递推关系的建立过程；感觉与递推问题具有相似之处；让我们来分析一下题目

1、守望者逃离

题目描述

魔法师家尤迪安充满野心

目前守望者拥有魔法初值 M ，其当前位置与岛屿出口的距离为 S 米；与此同时岛屿预计将在 T 秒后开始沉没。你的任务是编写一个程序来协助守望者计算其逃离荒岛所需最少时间；若无法成功脱险，则需输出守望者在剩余时间内所能达到的最大距离。根据上述参数进行分析时，请确保所有活动持续时间为整数秒；其中涉及的距离单位均为米（m），时间单位则统一采用秒（s）。

输入格式

共一行，包括空格隔开的三个非负整数 M ,S ,T 。

输出格式

共两行。

第11行为字符串“ _