走台阶

/*** 青蛙跳台阶** 要求：* 一只青蛙一次可以跳上1级台阶，也可以跳上2级。* 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。** 思路：* 如何跳上第n阶？* 方法一：在第n-1阶向上跳1级* 方法二：在第n-2阶向上跳2级* 所以跳上第n阶的跳法等于 跳上第n-1阶的跳法 加上 跳上第n-2阶的跳法*/
public class JumpFloor {//迭代版public static int JumpFloor2(int n) {if (n == 1 || n == 2) return n;int pre1 = 1;int pre2 = 2;int current = pre1 + pre2;for (int i = 3; i <= n; i++) {current = pre1 + pre2;pre1 = pre2;pre2 = current;}return current;}//递归版（时间复杂度2的阶乘太高）public static int JumpFloor1(int n) {if (n == 1 || n == 2) return n;return JumpFloor1(n - 1) + JumpFloor1(n - 2);}public static void main(String[] args) {System.out.println(JumpFloor2(1));System.out.println(JumpFloor2(2));System.out.println(JumpFloor2(3));System.out.println(JumpFloor2(4));}
}

走方格，总共有几种走法

/*** 问题一：方格从左上角走到右下角的走法数** https://www.cnblogs.com/qinyuguan/p/11473991.html* https://www.jianshu.com/p/9dda4fa0b4aa** 走格子问题* 有一个XxY的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。* 请设计一个算法，计算机器人有多少种走法。* 给定两个正整数int x,int y，请返回机器人的走法数目*/
public class MatrixPathWays {public static void main(String[] args) {System.out.println(countWays1(3, 5));System.out.println(countWays2(3, 5));System.out.println(countWays3(3, 5));}/*** 递归*/public static int countWays1(int x, int y) {if (x == 1 || y == 1)return 1;return countWays1(x - 1, y) + countWays1(x, y - 1);}/*** 动态规划一* 多算了一次[0][0]*/public static int countWays2(int x, int y) {int[][] dp = new int[x][y];//边界只有一种走法for (int row = 0; row < x; ++row) {dp[row][0] = 1;}//边界只有一种走法for (int column = 0; column < y; ++column) {dp[0][column] = 1;}//非边界for (int row = 1; row < x; ++row)for (int column = 1; column < y; ++column) {dp[row][column] = dp[row][column - 1] + dp[row - 1][column];}return dp[x - 1][y - 1];}/*** 动态规划2* 完美*/public static int countWays3(int x, int y) {int[][] dp = new int[x][y];for (int row = 0; row < x; ++row)for (int column = 0; column < y; ++column) {if (row == 0) {dp[0][column] = 1;} else if (column == 0) {dp[row][0] = 1;} else {dp[row][column] = dp[row][column - 1] + dp[row - 1][column];}}return dp[x - 1][y - 1];}
}

走方格，求最大最小值的路径

/*** 问题二：方格中的值表示某种意义，从左上角走到右下角时求最大值或者最小值的路径* https://blog.csdn.net/seagal890/article/details/88603064*/
public class MatrixPathMaxOrMin {/** 给定一个矩阵m，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，* 路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。* 例如：* {*      {1 3 5 9}*      {8 1 3 4}*      {5 0 6 1}*      {8 8 4 0}* }* 路径 1，3，1， 0,6，1，0 是所有路径中路径和最小的，所以返回12。* *//** 计算方法* */public static int minPathSum(int[][] matrixArr) {if (matrixArr == null || matrixArr.length == 0 ||matrixArr[0] == null || matrixArr[0].length == 0) {return 0;}int row = matrixArr.length;int col = matrixArr[0].length;int[][] dp = new int[row][col];//起点位置dp[0][0] = matrixArr[0][0];//边界位置for (int i = 1; i < row; i++) {dp[i][0] = dp[i - 1][0] + matrixArr[i][0];}//边界位置for (int j = 1; j < col; j++) {dp[0][j] = dp[0][j - 1] + matrixArr[0][j];}//其他位置for (int i = 1; i < row; i++) {for (int j = 1; j < col; j++) {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrixArr[i][j];}}return dp[row - 1][col - 1];}/*** 创建一个 M*N的矩阵，并赋予行和列随机整数值，元素的取值范围在1-10之间。*/public static int[][] createMatrix(int m, int n) {int[][] matrix = new int[m][n];int seed = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {seed = (int) ((Math.random() * 10) + 1);matrix[i][j] = seed;}}return matrix;}/** 输出矩阵* */public static void printMatrix(int[][] matrix) {for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {System.out.print(matrix[i][j] + "\t");}System.out.println();}}public static void main(String[] args) {int[][] matrix = createMatrix(3, 3);printMatrix(matrix);int sum = minPathSum(matrix);System.out.println("sum = " + sum);}}

走方格，有障碍，总共有几种走法

/*** https://www.cnblogs.com/qinyuguan/p/11474056.html* <p>* 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。* <p>* 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。* <p>* 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？* <p>* 网格中的障碍物和空位置分别用 1 和 0 来表示。* <p>* 说明：m 和 n 的值均不超过 100。*/
public class MatrixPathWithObstacles {public static void main(String[] args) {int[][] arr = {{0, 0, 0},{0, 0, 0},{0, 1, 0},};System.out.println(uniquePathsWithObstacles(arr));System.out.println(uniquePathsWithObstacles2(arr));}public static int uniquePathsWithObstacles(int[][] matrixArr) {int row = matrixArr.length;int column = matrixArr[0].length;int[][] dp = new int[row][column];dp[0][0] = 1;for (int i = 1; i < column; i++) {if (matrixArr[0][i] == 0) {dp[0][i] = dp[0][i - 1];}}for (int i = 1; i < row; i++) {if (matrixArr[i][0] == 0) {dp[i][0] = dp[i - 1][0];}}for (int i = 1; i < row; i++) {for (int j = 1; j < column; j++) {if (matrixArr[i][j] == 0) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[row - 1][column - 1];}public static int uniquePathsWithObstacles2(int[][] obstacleGrid) {int row = obstacleGrid.length;int column = obstacleGrid[0].length;int[][] dp = new int[row][column];for (int i = 0; i < column; i++) {if (obstacleGrid[0][i] == 1)break;dp[0][i] = 1;}for (int i = 0; i < row; i++) {if (obstacleGrid[i][0] == 1)break;dp[i][0] = 1;}for (int i = 1; i < row; i++) {for (int j = 1; j < column; j++) {if (obstacleGrid[i][j] == 1) {dp[i][j] = 0;} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[row - 1][column - 1];}}