算法——动态规划 怼烎@ 2021-11-27 02:52 359阅读 0赞 ### 文章目录 ### * * * 1.斐波那契数列 * * 1.1递归法 * 1.2动态规划 * 1.3优化法 * 2.变态青蛙跳台阶 * 3.最大连续子数组和 * 4.字符串分割 * 5.路径总数 * 6.路径总数(有障碍版) * 7.最小路径和 ### 1.斐波那契数列 ### #### 1.1递归法 #### class Test{ public int Fibonacci(int n){ if(n<=0){ return 0; } else if(n==1||n==2){ return 1; }else return Fibonacci(n-1)+Fibonacci(n-2); } } #### 1.2动态规划 #### //初始状态:f(1)=f(2)=1 //状态递推:f(n)=f(n-1)+f(n-2) //返回结果:f(n) class Test{ public int Fibonacci(int n){ if(n<=0){ return 0; } else if(n==1||n==2){ return 1; } int [] a = new int [n+1]; a[1]=a[2]=1; for(int i = 3;i<=n;i++){ a[i]=a[i-1]+a[i-2]; } return a[n]; } } #### 1.3优化法 #### class Test{ public int Fibonacci(int n){ if(n<=0){ return 0; } else if(n==1||n==2){ return 1; } int f1n=1; int f2n=1; int result = 0; for(int i = 3;i<=n;i++){ result = f1n+f2n; f1n = f2n; f2n = result; } return result; } } ### 2.变态青蛙跳台阶 ### 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多 少种跳法。 > **方法1:** > 跳n级台阶,第一步有n种跳法: > 跳1级,剩下n-1级,跳法为F(n-1) > 跳2级,剩下n-2级,跳法为F(n-2) > … > 跳n级,剩下0级,跳法为F(0) > So,F(n) = F(n-1)+F(n-2)+…+F(0) > F(n-1) = F(n-2)+F(n-3)+…+F(0) > F(n) = 2\*F(n-2) > \- > F(1) = 1 > F(2) = 2 > F(3) = 4 > … > F(n) = 2^(n-1) > **方法2** > 除了最后一级台阶必须要跳之外,其余每级台阶都有两种可能,所以F(n) = 2^(n-1) //方法1 class Test{ public int jumpFloor(int n){ return (int)Math.pow(2,n-1); } } //方法2 class Test{ public int jumpFloor(int n){ int total = 1; for(int i = 1;i<n;i++){ total*=2; } return total; } } //方法3 //降低时间复杂度 上述实现的时间复杂度:O(N) O(1)的实现:使用移位操作 class Test{ public int jumpFloor(int n){ return 1<<(n-1); } } ### 3.最大连续子数组和 ### > 子状态:以a\[i\]为末尾元素的子数组和的最大值 > f(i) = max( f(i-1)+a\[i\] , a\[i\] ) > f(i) = f(i-1)>0? f(i-1)+a\[i\] : a\[i\] > 初始值:f(0) = a\[0\] > 返回值:所有f(i)中的最大值 class Test{ public int FindGreatestSumOfSubArray(int [] a){ int sum = a[0]; int maxSum = a[0]; for (int i = 1;i<a.length;i++){ sum = sum>0 ? (sum+a[i]):a[i]; maxSum = sum>maxSum ? sum :maxSum; } return maxSum; } } ### 4.字符串分割 ### 给定一个字符串s和一个词典dict,确定s是否可以根据词典中的词分成 一个或多个单词。 比如,给定 s = “leetcode” dict = \[“leet”, “code”\] 返回true,因为"leetcode"可以被分成"leet code" public class Solution { public boolean wordBreak(String s, Set<String> dict) { boolean [] a = new boolean [s.length()+1]; a[0] = true; for (int i = 1;i <=s.length();i++){ for (int j = 0;j<i;j++){ if(a[j]&&dict.contains(s.substring(j,i))){ a[i]= true; break; } } } return a[s.length()]; } } ### 5.路径总数 ### 在一个m\*n的网格的左上角有一个机器人,机器人在任何时候只能向下或者向右移动, 机器人试图到达网格的右下角,有多少可能的路径。 public class Solution { public int uniquePaths(int m, int n) { int [][] a = new int [m][n]; for(int i = 0;i<m;i++) a[i][0] = 1; for(int i = 0;i<n;i++) a[0][i] = 1; for(int i = 1;i<m;i++){ for(int j = 1;j<n;j++){ a[i][j] = a[i-1][j]+a[i][j-1]; } } return a[m-1][n-1]; } } ### 6.路径总数(有障碍版) ### 机器人还是要从网格左上角到达右下角, 但是网格中添加了障碍物,障碍物用1表示。 > 动态规划: > 子状态:从(0,0)到(1,0)(1,1)…(m-1,n-1)…的路径总数 > F(i,j):从(0,0)到(i,j)的路径数 > 状态递推: > 如果(i,j)=1,则总数为0,否则为F(i-1,j)+F(i,j-1) > 特殊情况:第0行及第0列:1/0 public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int [][]a = new int [obstacleGrid.length][obstacleGrid[0].length]; for(int i = 0;i<a.length;i++){ if(obstacleGrid[i][0] == 1){ break; } a[i][0] = 1; } for(int i = 0;i<a[0].length;i++){ if(obstacleGrid[0][i] == 1){ break; } a[0][i] = 1; } for(int i = 1;i<a.length;i++){ for(int j = 1;j<a[0].length;j++){ if(obstacleGrid[i][j] == 1){ a[i][j] = 0; }else{ a[i][j] = a[i-1][j]+a[i][j-1]; } } } return a[a.length-1][a[0].length-1]; } } ### 7.最小路径和 ### 给定一个m\*n的网格,网格用非负数填充,找到一条从左上角到右下角的短路径。 注:每次只能向下或者向右移动。 public class Solution { public int minPathSum(int[][] grid) { int [][]a = new int[grid.length][grid[0].length]; a[0][0] = grid[0][0]; for(int i=1;i<grid.length;i++){ a[i][0] = a[i-1][0]+grid[i][0]; } for(int i=1;i<a[0].length;i++){ a[0][i] = a[0][i-1]+grid[0][i]; } for(int i=1;i<a.length;i++){ for(int j=1;j<a[0].length;j++){ a[i][j] = Math.min(a[i-1][j],a[i][j-1])+grid[i][j]; } } return a[a.length-1][a[0].length-1]; } }
还没有评论,来说两句吧...