【动态规划】Fibonacci、跳台阶、变态跳台阶、矩形覆盖、最大连续子数组的和、不同路径、最小路径和、triangle
文章目录
- 动态规划
- Fibonacci
- 跳台阶
- 变态跳台阶
- 矩形覆盖
- 最大连续子数组的和
- 不同路径
- 不同路径二
- 最小路径和
- triangle
- word-break 单词分割
动态规划
动态规划通俗的来讲就是大事化小、小事化了
在将大问题化解为小问题的分治过程中，保存这些小问题的结果，供后面处理更大规模问题时使用。
动态规划问题的特点:
- 可以将原来的问题分解成几个相似的子问题
- 所以的子问题都只需要解决一次
- 存储子问题的解
动态规划问题一般从四个方面解决:
- 状态定义
- 状态间的转移方程定义
- 状态的初始化
- 返回结果
动态规划的本质就是状态的定义和状态转移方程的定义
Fibonacci
斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
方法一:递归
public class Solution {public int Fibonacci(int n) {if(n == 0)return 0;if(n <= 2)return 1;return Fibonacci(n-1)+Fibonacci(n-2);}
}
递归方法的时间复杂度为O(2n) ，随着n的增大呈现指数增长、效率低下，容易导致栈溢出、并且有大量的重复计算
方法二:动态规划
- 状态: 第n项的斐波那契值F(n)
- 状态转移方程:第n项的斐波那契值 = 第n-1项的斐波那契值+第n-2项的斐波那契值 相当于F(n) = F(n-1)+F(n-2)
- 状态初始化: F(1) = F(2) = 1
- 返回结果:F(n)
public class Solution {public int Fibonacci(int n) {if(n == 0)return 0;if(n <= 2)return 1;//用于存放第i项的值int []arr = new int[n];//初始状态arr[0] = 1;arr[1] = 1;for(int i = 2; i < n;i++){//状态转移方程arr[i] = arr[i-1] + arr[i-2];}//返回值return arr[n-1];}
}
上述动态规划的空间复杂度为0(n)，开辟了一个数组存放第i项的斐波那契值，但其实F(n)只与它的前两项有关，所以没有必要保存所有子问题的解，只要保存两个子问题的解即可。
方法三:动态规划
public class Solution {public int Fibonacci(int n) {if(n == 0)return 0;if(n <= 2)return 1;int first = 1;int second = 1;int result = 1;for(int i = 3; i <= n;i++){result = first+second;first = second;second = result;}return result;}
}
跳台阶
跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
动态规划法
- 状态
- 假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1)
- 假定第一次跳的是二阶，那么剩下的是n-2个台阶，跳法是f(n-2)
- 状态转移方程: f(n)=f(n-1)+f(n-2)
- 状态初始化: f(1)=1 f(2) = 2
- 返回结果:f(n)
- 最终发现状态方程与斐波那契数列数列相似
public class Solution {public int JumpFloor(int target) {if(target == 1)return 1;if(target == 2)return 2;return JumpFloor(target-1)+JumpFloor(target-2);}
}
public class Solution {public int JumpFloor(int target) {if(target == 1)return 1;if(target == 2)return 2;int first = 1;int second = 2;int result = 0;for(int i = 3; i <= target;i++){result = first+second;first = second;second = result;}return result;}
}
变态跳台阶
变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多
少种跳法。
动态规划法
- 状态
- 假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1)
- 假定第一次跳的是二阶，那么剩下的是n-2个台阶，跳法是f(n-2)
- 假定第一次跳的是三阶，那么剩下的是n-3个台阶，跳法是f(n-3)
- ………………
- 假定第一次跳的是n阶，那么剩下的是0个台阶，跳法是f(0)
- 状态转移方程: f(n)=f(n-1)+f(n-2)+f(n-3)+………+f(0)
- 看到此方程我们仍无法解答我们可以试着写出f(n-1)
- f(n-1)=f(n-2)+f(n-3)+f(n-4)+……f(0)
- 可以得出f(n) = 2*f(n-1)
- 状态初始化: f(1)=1
- 返回结果:f(n)
方法一:动态规划
public class Solution {public int JumpFloorII(int target) {if(target == 1)return 1;int first = 1;int result = 0;for(int i = 2; i <= target;i++){result = 2*first;first = result;}return result;}
}
方法二:数学排列组合思路
每个台阶看成一个位置，除了最后一个位置之后，每个台阶都有两种情况(跳或者不被跳)
所以排列数 = 2(n-1)
public class Solution {public int JumpFloorII(int target) {return (int)Math.pow(2,target-1);}
}
矩形覆盖
矩形覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
- 状态
- 假定第一个矩形横着放，那么剩下的矩形有f(n-1）种摆法
- 假定第一个矩形竖着着放，那么剩下的矩形有f(n-2）种摆法
- 状态转移方程: f(n)=f(n-1)+f(n-2)
- 状态初始化: f(1)=1 f(2)=2
- 返回结果:f(n)
public class Solution {public int RectCover(int target) {if(target == 1)return 1;if(target == 2)return 2;int first = 1;int second = 2;int result = 0; for(int i = 3 ; i <= target;i++){result = first+second;first = second;second = result;}return result;}
}
最大连续子数组的和
最大连续子数组的和
输入一个整形数组（可能有正数和负数），求数组中连续子数组（最少有一个元素）的最大和。要求时间复杂度为O(n)。
- 状态
- 子状态: 长度为1,2，3……n的子数组的最大值
- F(i) ：以arr[i]为末尾元素的子数组和的最大值了
- 状态转移方程
- F(i) = Math.max(F(i-1)+arr[i],arr[i])
- F(i) = （F(i-1) > 0）? F(i-1) + array[i] : array[i]
- 初始值:F(0) = array[0]
- 返回值:所有F(i)中的最大值
import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] arr = new int[n];for(int i = 0 ; i < n;i++){arr[i] = sc.nextInt();}System.out.println(max(arr));}private static int max(int []arr){int len = arr.length;if(len == 0)return 0;if(len == 1)return arr[0];int []result = new int[len];result[0] = arr[0];int max = arr[0];for(int i = 1;i < len;i++){result[i] = (result[i-1] > 0)? result[i-1]+arr[i] :arr[i];max = Math.max(max,result[i]);}return max;}
}
不同路径
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
动态规划
- 状态
- 假设机器人到达(i,j)点、机器人能到达此点，只有两种情况:从上面到达(i,j)、从左边到达(i,j)
- 状态转移方程 F[i,j] = F[i,j-1]+F[i-1,j]
- 初始化
- 第一行和第一列比较特殊 因为只有一直向右走或者一直向下走才会到达F[0,j] = F[i,0] = 1
- 返回值 F[ row-1 ] [ col-1]
class Solution {public int uniquePaths(int m, int n) {int[][] path = new int[m][n];//初始化for(int i = 0 ; i < m;i++){path[i][0] = 1;}for(int i = 1 ; i < n;i++){path[0][i] = 1;}//状态转移for(int i = 1; i < m;i++){for(int j = 1;j < n;j++){path[i][j] = path[i][j-1]+path[i-1][j];}}return path[m-1][n-1];}
}
不同路径二
不同路径2
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
有1的地方不能走哦
动态规划
- 状态
- 假设机器人可以到达(i,j)点、机器人能到达此点，只有两种情况:从上面到达(i,j)、从左边到达(i,j)
- 状态转移方程
- 无障碍物：F[i,j] = F[i,j-1]+F[i-1,j]
- 有障碍物：F[i,j] = 0
- 初始化
- 第一行和第一列比较特殊 因为只有一直向右走或者一直向下走才会到达F[0,j] = F[i,0] = 1 但是此时若遇到障碍物后面的结点均不可达
- 返回值 F[ row-1 ] [ col-1]
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {if(obstacleGrid == null || obstacleGrid[0][0] == 1)return 0;int row = obstacleGrid.length;int col = obstacleGrid[0].length;//初始化for(int i = 0 ; i < row;i++){if(obstacleGrid[i][0] == 0){obstacleGrid[i][0] = 1;}else{obstacleGrid[i][0] = 0;for(i = i+1;i < row;i++){obstacleGrid[i][0] = 0;}}}for(int i = 1 ; i < col;i++){if(obstacleGrid[0][i] == 0){obstacleGrid[0][i] = 1;}else{obstacleGrid[0][i] = 0;for(i= i+1;i < col;i++){obstacleGrid[0][i] = 0;}}}//状态转移方程for(int i = 1; i < row;i++){for(int j = 1;j < col;j++){obstacleGrid[i][j] = (obstacleGrid[i][j] == 0) ? obstacleGrid[i-1][j]+obstacleGrid[i][j-1]:0;}}return obstacleGrid[row-1][col-1];}
}
最小路径和
最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
- 状态
- 假设坐标上随机一点(i,j)点、到达此点时只有两种情况:从上面到达(i,j)、从左边到达(i,j)，那么到达此点的最小路径就是Math.min(F[i,j-1],F[i-1,j) + F[i][j]
- 状态转移方程Math.min(F[i,j-1],F[i-1,j) + F[i][j]
- 初始化
- 第一行和第一列比较特殊 因为只有一直向右走或者一直向下走 F[0,j] += F[0,j-1] F[i,0] += F[i-1,0]
- 返回值 F[ row-1 ] [ col-1]
class Solution {public int minPathSum(int[][] grid) {if(grid == null)return 0;int row = grid.length;int col = grid[0].length;//初始化for(int i = 1 ; i < row;i++){grid[i][0] += grid[i-1][0]; }for(int i = 1 ; i < col;i++){grid[0][i] += grid[0][i-1]; }//动态规划for(int i = 1; i < row;i++){for(int j = 1;j < col;j++){grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);}}return grid[row-1][col-1];}
}
triangle
triangle
给定一个三角形，找出从顶到底的最小路径和，每一步可以从上一行移动到下一行相邻的数字
动态规划
- 状态
- 假设到达(i,j)点、能到达此点，只有两种情况:从上面的点到达(i,j)、从上面的左边的点到达(i,j)
- 状态转移方程 F[i,j] = F[i-1,j-1]+F[i-1,j]
- 初始化
- 第一列比较特殊 因为只有一直向下走才会到达F[0,j] += F[i-1,0]
- 每行的最后一个元素也比较特殊，只有上面的左边的点才会到达
- 返回值 :最后一行的最小值
import java.util.*;
public class Solution {public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {if(triangle == null) return 0;int row = triangle.size();int col = triangle.get(triangle.size()-1).size();int [][]dp = new int[row][col];int r = 0;//将集合中的元素挪到数组中for(ArrayList<Integer> list:triangle){for(int i = 0; i < list.size();i++){dp[r][i] = list.get(i);}r++;}//初始化for(int i = 1; i < row;i++){dp[i][0] += dp[i-1][0];}for(int i = 1; i < row;i++){dp[i][i] += dp[i-1][i-1];}//状态转移for(int i =1 ; i < row;i++){for(int j = 1; j < i;j++){dp[i][j] += Math.min(dp[i-1][j],dp[i-1][j-1]);}}int min = Integer.MAX_VALUE;for(int i = 0 ; i < col ;i++){if(dp[row-1][i] < min){min = dp[row-1][i];}}return min;}
}
word-break 单词分割
work-break
题目描述
给定一个字符串和一个词典dict，确定s是否可以根据词典中的词分成 一个或多个单词。
比如，给定
s = “leetcode”
dict = [“leet”, “code”]
返回true，因为"leetcode"可以被分成"leet code"
动态规划
- 状态 假设对于字符串s，我们到下标i的位置，如果该字符串可分割，那么下标(0,i-1)所表示的字符串在字典中并且下标i之后的字符串也在字典中
- 状态转移方程 F(i) = F(i-1) && s.substring(i)在字典中
- 初始化 F(-1) = true
- 返回结果 F(n)
未完待续……
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！