53. 最大子序和

题目描述给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。解题思路动态规划转移方程: f(i)=max{f(i−1)+nums[i],nums[i]} static int maxSubArray(int[] nums) { i


122. 买卖股票的最佳时机 II

题目描述给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)


646. 最长数对链

题目描述给出 n 个数对。 在每一个数对中,第一个数字总是比第二个数字小。现在,我们定义一种跟随关系,当且仅当 b < c 时,数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。给定一个数对集合,找出能够形成的最长数对链的长度。你不需要用到所有的数对,你可以以任


300. 最长递增子序列

题目描述给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余> 元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。解题思路:dp[i] 表示以 nums[i] 这个数结尾的最


279. 完全平方数

题目描述给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ,返回和为 n 的完全平方数的最少数量 。解题思路:dp[n]:和为 n 的完全平方数的最少数量状态转移方程:dp[n]=1+min d


343. 整数拆分

题目描述给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。解题思路:dp[i]定义:将正整数 i拆分成至少两个正整数的和之后,这些正整数的最大乘积令 k 是拆分出的第一个正整数,则剩下的部分是n−k,n−k可以不继续拆分,或者继续拆分成至少两个正


413. 等差数列划分

题目描述给你一个整数数组 nums ,返回数组 nums 中所有为等差数组的 子数组 个数。子数组(至少有三个元素)是数组中的一个连续序列。解题思路:dp[i]含义:以 A[i]为结尾的等差递增子区间的个数递增子区间不一定以最后一个元素为结尾,可以是任意一个元素结尾,因此需要返回 dp 数组累加的结


62. 不同路径

题目描述一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?解题思路:临界条件是仅有一行或仅有一列,此时路径应该为1定义数组dp[i]


64. 最小路径和

题目描述给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明:每次只能向下或者向右移动一步。解题思路:第一行与第一列的路径和就是当前行(列)的数字总和dp[i][0] = dp[i - 1][0] + grid[i][0];第一行d


213. 打家劫舍 II

题目描述你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组,计算你