作业题
初始化：dp[0][0~width] = 1, dp[0~height][0] = 1.
递推公式： dp[i][j] = dp[i - 1][j] + dp[i][j - 1] ( i>= 1, j >= 1)
package jjn.carl.dp;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/6 14:58 */public class LeetCode62 { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < n; i++) { dp[0][i] = 1; } for (int i = 0; i < m; i++) { dp[i][0] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int m = scanner.nextInt(); int n = scanner.nextInt(); int uniquePaths = new LeetCode62().uniquePaths(m, n); System.out.println(uniquePaths); }}
复制代码
初始化：dp[0][0~width] = 1, dp[0~height][0] = 1.
递推公式：
如果
obstacleGrid[i][j] == 0:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] ( i>= 1, j >= 1)
obstacleGrid[i][j] == 1:
dp[i][j] = 0
package jjn.carl.dp;
import jjn.round1.LeetCode171_ExcelSheetColumnNumber;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/6 15:04 */public class LeetCode63 { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int height = obstacleGrid.length, width = obstacleGrid[0].length; int[][] dp = new int[height][width]; for (int i = 0; i < height; i++) { if (obstacleGrid[i][0] == 1) { for (int j = i; j < height; j++) { dp[j][0] = 0; i = j; } } else { dp[i][0] = 1; } } for (int i = 0; i < width; i++) { if (obstacleGrid[0][i] == 1) { for (int j = i; j < width; j++) { dp[0][j] = 0; i = j; } } else { dp[0][i] = 1; } } for (int i = 1; i < height; i++) { for (int j = 1; j < width; j++) { if (obstacleGrid[i][j] == 1) { dp[i][j] = 0; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[height - 1][width - 1]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int height = scanner.nextInt(); int width = scanner.nextInt(); int[][] obstacleGrid = new int[height][width]; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { obstacleGrid[i][j] = scanner.nextInt(); } } int uniquePathsWithObstacles = new LeetCode63().uniquePathsWithObstacles(obstacleGrid); System.out.println(uniquePathsWithObstacles); }}
复制代码
评论