我已经多次面试挂在动态规划算法上，俗话说人不能总在同一棵树上吊死，所以本篇刷遍动态规划算法的easy和medium，hard还需慢慢修炼。这篇将持续更新。
5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。示例 2：
输入: "cbbd"
输出: "bb"思路
动态规划的思想，比如CABAC，如果只有一个字符‘B’，那么一定是回文的，然后看B两边，如果“ABA”两边相同，那么是回文的；再看“ABA”的两边。一直到左右两边不相等，或者溢出。和之前存储的回文串长度比较。
考虑示例1和示例2两种情况。
代码
class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length()<1)
return "";
int start = 0;
int end = 0;
for(int i=0;i<s.length();i++){
int len1 = expandAroundCenter(s,i,i); //以一个字符为中心
int len2 = expandAroundCenter(s,i,i+1); //以两个字符为中心
int len = Math.max(len1,len2);
if(len > end-start){
start = i-(len-1)/2;
end = i+len/2;
}
}
return s.substring(start,end+1);
}
public int expandAroundCenter(String s, int left, int right){
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
left--;
right++;
}
return right-left-1;
}
}53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6。解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路
动态规划问题。定义一个存储答案的ans并初始化，sum为存储最大子序和的一个变量，遍历数组，sum只要大于0就一直加，如果sum小于0，将当前数字赋给sum，ans每次存储sum 和 ans的最大值即可。
代码
class Solution {
public int maxSubArray(int[] nums) {
int sum = 0;
int ans = nums[0];
for (int i = 0; i < nums.length; i++) {
if (sum > 0)
sum += nums[i];
else
sum = nums[i];
ans = Math.max(ans, sum);
}
return ans;
}
}62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右示例 2:
输入: m = 7, n = 3
输出: 28思路
动态规划问题，首先一行或一列的情况下，只有一种走法；
其他情况=它上面的格子的走法数量+它左边格子的走法数量
代码
class Solution {
public int uniquePaths(int m, int n) {
if(m<0 || n<0)
return 0;
int[][] record = new int[m][n];
for(int i=0;i<m;i++)
record[i][0]=1;
for(int j=1;j<n;j++)
record[0][j]=1;
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
record[i][j]=record[i-1][j]+record[i][j-1];
}
}
return record[m-1][n-1];
}
}
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。说明：m 和 n 的值均不超过 100。
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右思路：将障碍物所在的位置标记为0。
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int[][] record = new int[obstacleGrid.length][obstacleGrid[0].length];
int i=0;
int j=0;
for(i=0;i<obstacleGrid.length;i++){
for(j=0;j<obstacleGrid[0].length;j++){
if(obstacleGrid[i][j]==1)
record[i][j] = 0;
else if(i==0 && j==0)
record[i][j] = 1;
else if(i==0 && j>0)
record[i][j]=record[i][j-1];
else if(j==0 && i>0)
record[i][j]=record[i-1][j];
else
record[i][j]=record[i-1][j]+record[i][j-1];
}
}
return record[i-1][j-1];
}
}64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] record = new int[m][n];
int i=0,j=0;
for(i=0;i<m;i++){
for(j=0;j<n;j++){
if(i==0 && j==0)
record[i][j]=grid[i][j];
else if(i==0 && j>0)
record[i][j]=grid[i][j]+record[i][j-1];
else if(j==0 && i>0)
record[i][j]=grid[i][j]+record[i-1][j];
else
record[i][j]=Math.min(record[i-1][j],record[i][j-1])+grid[i][j];
}
}
return record[i-1][j-1];
}
}70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶思路
典型的动态规划问题，对于第n阶台阶来说，有两种办法，一种是爬一个台阶，到第n-1阶；第二种是爬两个台阶，到第n-2阶。
得出动态规划递推式： F(n)=F(n-1)+F(n-2)
代码
class Solution {
public int climbStairs(int n) {
if(n<0) return 0;
if(n==1) return 1;
if(n==2) return 2;
int[] res = new int[n];
res[0]=1;
res[1]=2;
for(int i=2;i<n;i++)
res[i]=res[i-1]+res[i-2];
return res[n-1];
}
}91. 解码方法
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
代码
class Solution {
public int numDecodings(String s) {
if (s.charAt(0) == '0') return 0;
if (s.length() == 1) return 1;
int n0 = 1;
int n1 = 1;
int a,b;
for (int i = 1; i < s.length(); i++) {
if(s.charAt(i)=='0')
a=0;
else
a=n1;
if(s.charAt(i-1) == '1' || (s.charAt(i-1) == '2' && s.charAt(i) <= '6'))
b=n0;
else
b=0;
n0 = n1;
n1 = a + b;
}
return n1;
}
}96. 不同的二叉搜索树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3思路
n = 0 时赋为1
dp[2] = dp[0] * dp[1] (1为根的情况)
+ dp[1] * dp[0] (2为根的情况)
同理可写出 n = 3 的计算方法：
dp[3] = dp[0] * dp[2] (1为根的情况)
+ dp[1] * dp[1] (2为根的情况)
+ dp[2] * dp[0] (3为根的情况)代码
class Solution {
public int numTrees(int n) {
if(n == 0 || n == 1)
return 1;
int[] nums = new int[n+1]; //申请n+1个空间是因为空子树也是一种形式
nums[0] = 1; //该子树为空或只有一个节点，都只有一种解法
nums[1] = 1;
for(int i = 2;i <= n;i++) { //动态规划，从n = 2开始循环，一直到 n
for(int j = 0;j < i;j++) { //j作为根节点时,其中j = 1时左子树为空,j = i时右子树为空
nums[i] += nums[j]*nums[i-j-1];
}
}
return nums[n];
}
}95. 不同的二叉搜索树 II
给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。
示例:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3思路
递归。首先来计数需要构建的二叉树数量。可能的二叉搜素数数量是一个 卡特兰数。我们跟随上文的逻辑，只是这次是构建具体的树，而不是计数。
我们从序列 1 ..n 中取出数字 i，作为当前树的树根。于是，剩余 i – 1 个元素可用于左子树，n – i 个元素用于右子树。如 前文所述，这样会产生 G(i – 1) 种左子树 和 G(n – i) 种右子树，其中 G 是卡特兰数。现在，我们对序列 1 … i – 1 重复上述过程，以构建所有的左子树；然后对 i + 1 … n 重复，以构建所有的右子树。这样，我们就有了树根 i 和可能的左子树、右子树的列表。最后一步，对两个列表循环，将左子树和右子树连接在根上。
class Solution {
public LinkedList<TreeNode> generate_trees(int start, int end) {
LinkedList<TreeNode> all_trees = new LinkedList<TreeNode>();
if (start > end) {
all_trees.add(null);
return all_trees;
}
// pick up a root
for (int i = start; i <= end; i++) {
// all possible left subtrees if i is choosen to be a root
LinkedList<TreeNode> left_trees = generate_trees(start, i - 1);
// all possible right subtrees if i is choosen to be a root
LinkedList<TreeNode> right_trees = generate_trees(i + 1, end);
// connect left and right trees to the root i
for (TreeNode l : left_trees) {
for (TreeNode r : right_trees) {
TreeNode current_tree = new TreeNode(i);
current_tree.left = l;
current_tree.right = r;
all_trees.add(current_tree);
}
}
}
return all_trees;
}
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new LinkedList<TreeNode>();
}
return generate_trees(1, n);
}
}120. 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。代码
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==0) return 0;
int n = triangle.size();
int[] dp = new int[n+1];
for(int i=n-1;i>=0;i--){
for(int j=0;j<=i;j++){
dp[j]=Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}121. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例1：
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例2：
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。思路：
一次循环，在价格最低的时候买入，在价格最高的时候卖出，将最大的利润保存下来。
代码：
class Solution {
public int maxProfit(int[] prices) {
if(prices.length==0)
return 0;
int min_prices = prices[0];
int max_profit = 0;
for(int i = 0;i<prices.length;i++){
min_prices = Math.min(min_prices, prices[i]);
max_profit = Math.max(max_profit, prices[i] - min_prices);
}
return max_profit;
}
}139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false思路
这个方法的想法是对于给定的字符串s可以被拆分成子问题 s1和 s2 。如果这些子问题都可以独立地被拆分成符合要求的子问题，那么整个问题 s 也可以满足。也就是，如果 "catsanddog" 可以拆分成两个子字符串 "catsand" 和 "dog" 。子问题 "catsand" 可以进一步拆分成 "cats" 和 "and" ，这两个独立的部分都是字典的一部分，所以 "catsand" 满足题意条件，再往前， "catsand" 和 "dog" 也分别满足条件，所以整个字符串 "catsanddog" 也满足条件。
现在，我们考虑 dp 数组求解的过程。我们使用 n+1大小数组的dp ,其中 n 是给定字符串的长度。我们也使用 2 个下标指针 i 和 j，其中 i是当前字符串从头开始的子字符串s'的长度，j 是当前子字符串s'的拆分位置，拆分成 s'(0,j) 和 s'(j+1,i) 。为了求出 dp 数组，我们初始化dp[0] 为 true ，这是因为空字符串总是字典的一部分。dp 数组剩余的元素都初始化为false。我们用下标 i来考虑所有从当前字符串开始的可能的子字符串。对于每一个子字符串，我们通过下标 j将它拆分成 s1'和 s2'（注意 i现在指向 s2'的结尾）。为了将dp[i] 数组求出来，我们依次检查每个dp[j] 是否为 true ，也就是子字符串 s1'是否满足题目要求。如果满足，我们接下来检查 s2'是否在字典中。如果包含，我们接下来检查 s2' 是否在字典中，如果两个字符串都满足要求，我们让 dp[i] 为true ，否则令其为false 。
代码
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet=new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}152. 乘积最大子序列
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。我们先定义一个数组 dpMax，用 dpMax[i] 表示以第 i 个元素的结尾的子数组，乘积最大的值，也就是这个数组必须包含第 i 个元素。
那么 dpMax[i] 的话有几种取值。
当 nums[i] >= 0 并且dpMax[i-1] > 0，dpMax[i] = dpMax[i-1] * nums[i]
当 nums[i] >= 0 并且dpMax[i-1] < 0，此时如果和前边的数累乘的话，会变成负数，所以dpMax[i] = nums[i]
当 nums[i] < 0，此时如果前边累乘结果是一个很大的负数，和当前负数累乘的话就会变成一个更大的数。所以我们还需要一个数组 dpMin 来记录以第 i 个元素的结尾的子数组，乘积最小的值。
当dpMin[i-1] < 0，dpMax[i] = dpMin[i-1] * nums[i]
当dpMin[i-1] >= 0，dpMax[i] = nums[i]
当然，上边引入了 dpMin 数组，怎么求 dpMin 其实和上边求 dpMax 的过程其实是一样的。
按上边的分析，我们就需要加很多的 if else来判断不同的情况，这里可以用个技巧。
我们注意到上边dpMax[i] 的取值无非就是三种，dpMax[i-1] * nums[i]、dpMin[i-1] * nums[i] 以及 nums[i]。
所以我们更新的时候，无需去区分当前是哪种情况，只需要从三个取值中选一个最大的即可。
dpMax[i] = max(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]);
求 dpMin[i] 同理。
dpMin[i] = min(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]);
更新过程中，我们可以用一个变量 max 去保存当前得到的最大值。
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
if(n<=0) return 0;
int[] dpMax = new int[n];
dpMax[0] = nums[0];
int[] dpMin = new int[n];
dpMin[0] = nums[0];
int max = nums[0];
for(int i=1; i<n; i++){
dpMax[i] = Math.max(dpMin[i-1]*nums[i],Math.max(dpMax[i-1]*nums[i],nums[i]));
dpMin[i] = Math.min(dpMin[i - 1] * nums[i], Math.min(dpMax[i - 1] * nums[i], nums[i]));
max = Math.max(max, dpMax[i]);
}
return max;
}
}198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例1：
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例2：
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。思路
当前最大的累计收益= max(前一家的收益，前前一家的收益加上当前的收益)
状态转移方程： dp[i] = max(dp[i-1], dp[i-2]+nums[i])
代码
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n==0)
return 0;
if(n==1)
return nums[0];
int dp[] = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i= 2;i<n;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[n-1];
}
}213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。思路：和上一题的区别是，此题的房间首尾相连，偷第一家就不能偷最后一家，偷最后一家就不能偷第一家，相当于偷[0,n-2]或者[1,n-1]。
class Solution {
public int rob(int[] nums) {
int n=nums.length;
if(n==0)
return 0;
if(n==1)
return nums[0];
if(n==2)
return Math.max(nums[0],nums[1]);
return Math.max(helper(nums,0,n-2),helper(nums,1,n-1));
}
public int helper(int[] nums, int start, int end){
int[] dp = new int[end-start+1];
dp[0] = nums[start];
dp[1] = Math.max(nums[start],nums[start+1]);
for(int i=start+2;i<=end;i++){
dp[i-start] = Math.max((dp[i-start-2]+nums[i]),dp[i-start-1]);
}
return dp[end-start];
}
}
暂无评论内容