m x n 网格上有一个机器人。机器人最初位于左上角（即 grid[0][0]）。机器人尝试移动到右下角（即 grid[m - 1][n - 1]）。机器人在任何时间点只能向下或向右移动。
给定两个整数 m 和 n，返回机器人到达右下角可能采取的唯一路径的数量。
生成的测试用例的答案将小于或等于 2 * 109。
示例1：
输入：m = 3，n = 7
输出：28
示例2：
输入：m = 3，n = 2
输出：3
说明：从左上角开始，到达右下角一共有3种方式：
限制：
1 原始页面
我们可以使用这个手写数组模拟来探索模式（顺便原谅我糟糕的笔迹）。
public int uniquePaths(int m, int n) {
if(n<=1 || m<=1){
return 1;
}
int dp[][] = new int[m+1][n+1];
dp[0][1] = 1;
for(int i=1; i<m+1; i++){
for(int j=1; j<n+1; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m][n];
}
dp[0][1] = 1;对于这段代码，实际上我们使用 dp[1][0] = 1 还是 dp[0][1] = 1 并不重要，因为我们想要将索引匹配到 m 和 n，我们再扩展一行并当我们初始化数组时看到的列： int dp[][] = new int[m+1][n+1];
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int row = obstacleGrid.length;
int col = obstacleGrid[0].length;
int[][] dp = new int[row][col];
boolean isBlocked = false;
for(int i=0; i<row; i++){
if(obstacleGrid[i][0]==1){
isBlocked = true;
}
dp[i][0] = isBlocked ? 0 : 1;
}
isBlocked = false;
for(int i=0; i<col; i++){
if(obstacleGrid[0][i]==1){
isBlocked = true;
}
dp[0][i] = isBlocked ? 0 : 1;
}
for(int i=1; i<row; i++){
for(int j=1; j<col; j++){
if(obstacleGrid[i][j] == 1){
dp[i][j] = 0;
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
// Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
return dp[row-1][col-1];
}
没有什么特别难实现的，我们只需要考虑被遮挡的东西就可以了，但是很容易想到，这意味着当有遮挡的时候，被遮挡的左边或者下面的格子是不能被通过这个方向到达。 （A格子左边的格子是被封锁的，我们无法从A的左边移动到A，只能找到向上的路线，这个逻辑也适用于向上）
给定一个整数 n，将其分解为 k 个正整数之和，其中 k >= 2，并最大化这些整数的乘积。
返回您可以获得的最大产品。
示例1：
输入：n = 2
输出：1
解释：2 = 1 + 1, 1 × 1 = 1.
示例2：
输入：n = 10
输出：36
解释：10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
限制：
2
原始页面
public int integerBreak(int n) {
if(n<=2){
return 1;
}
//init
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 1;
//logic
for(int i=3; i<=n; i++){
for(int num=1; num<i; num++){
dp[i] = Math.max(
Math.max(num * (i - num), dp[i]),
num * dp[i - num]);
}
}
// Arrays.stream(dp).forEach(System.out::println);
return dp[dp.length-1];
}
以上是LeetCode Day动态编程第 2 部分的详细内容。更多信息请关注PHP中文网其他相关文章！
