十五周算法训练营——普通动态规划（上）

,斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：,F(0) = 0，F(1) = 1 F(n) = F(n – 1) + F(n – 2)，其中 n > 1 给定 n ，请计算 F(n) 。,示例 1：,输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1,给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。,计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。,你可以认为每种硬币的数量是无限的。,示例 1：,输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1,给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。,说明：每次只能向下或者向右移动一步。,示例 1：,
,,输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。,Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。,游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。,Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。,假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。,示例 1：,输入：piles = [5,3,4,5] 输出：true 解释： Alice 先开始，只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。 如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。 如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。 这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。,给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。,子数组 是数组中的一个连续部分。,示例 1：,输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。,给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。,你可以对一个单词进行如下三种操作：,插入一个字符 删除一个字符 替换一个字符,示例 1：,输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)