一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。 示例 1:
示例 2:
提示:
本题其实就是将上一题的代码照搬过来 ,然后加上一个限制条件, 给了一个障碍物, 碰到障碍物就必须另寻它路。 当然题中没有排除左上角 和 右下角是否有障碍物的情况, 所以我们还需要做判断。
按照卡哥的动态规划五部曲的思路来进行解题
dp[i][j]
: 表示 从(0,0) 到 (i,j) 一共有dp[i][j]
个方法 这是可以根据题意和按照对动态规划的掌握 来进行推导的。 如果刚开始没有接触过动态规划 ,那么还是需要按照卡哥的《代码随想录》系统的学习一下。
因为规定了只能向右或者向下走 ,所以
dp[i][j]
可以是通过dp[i-1][j]
和dp[i][j-1]
相加推导出来的 所以:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
本题的初始化算是非常友好的了 ,从(0,0) 开始 ,同时他只能向右或者向下走 。所以初始化可以是
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
将顺着向右 和 顺着向下的路都初始化成1 , 因为只能一次走一格。 如果遇到obstacleGrid[0][j] == 1
或者obstacleGrid[i][0] == 1
的情况直接初始化成为 0即可。 也就是不需要做处理 ,因为有障碍物说明这条路已经行不通了 。
从(0,0)
到(i,j)
,就需要使用两层for 循环将其挨个遍历 ,如果遇到obstacleGrid[i][j] == 1
的情况 ,直接continue
即可。
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
//如果在起点或终点出现了障碍,直接返回0
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1)
return 0;
int [][]dp = new int[m][n];
for(int i= 0 ; i< m && obstacleGrid[i][0] == 0 ;i++){
dp[i][0] = 1;
}
for(int j= 0 ; j< n && obstacleGrid[0][j] == 0; j++){
dp[0][j] = 1;
}
for(int i = 1;i< m; i++){
for(int j =1 ;j < n ;j++){
if(obstacleGrid[i][j] == 1){
continue;
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
}
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1:
示例 2:
先对题目进行拆分 ,dp[i]
可以定义为 对整数i 进行拆分 ,可以得到乘积最大,最大乘积为dp[i]
本题的拆分可以进行很多次, 要求最少是用两次, 我们这里可以使用另一个变量j
如果整数i 拆分得到的一个数为j 那么另一个就是i-j
他们的乘积就是j*(i-j)
。这样就是拆分成两个。 如果拆分为多个, 那么就是将(i-j)
再继续进行拆分。j * dp[i - j]
是拆分成两个以及两个以上的个数相乘。
所以得到的递推公式就是dp[i][j] = Math.max(dp[i][j], Math.max(j*(i-j), j*dp[i-j]))
所以按照顺序就可以进行遍历得到最大乘积。
class Solution {
public int integerBreak(int n) {
int []dp =new int[n+1];
// 如果拆分为两个数 那么拆分乘积就是 j * (i-j)
//如果拆分为更多的数, 那么拆分乘积就是 j * dp[i-j]
// 我们需要做的就是找出拆分乘积最大的数
//初始化
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
for(int i = 3;i <= n;i++){
for(int j = 1; j < i-1; j++){
dp[i] = Math.max(dp[i],Math.max(j*(i-j) , j*dp[i-j]));
}
}
return dp[n];
}
}
给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种? 示例:
本题刚开始我并没有想到用动态规划能够怎么想出思路。 也是看了题解之后才理解的。 一开始我认为需要构建好二叉搜索树才能看出有什么规律, 但是写了几个之后并没有什么发现, 索性就战术性后退了。
n == 1的时候有1 个 n == 2 的时候 有 2 种, n == 3的 时候 有5 种….
代码随想录 (programmercarl.com) 之后的就是看卡哥题解了。
dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
之后 ,还是按照上一题的思路 ,用另一个变量 j 作为左边的数量,然后 (i-j)作为右边的数量, 然后按照上面推出来的规律进行解就可以了
class Solution {
public int numTrees(int n) {
if(n ==1 && n ==2){
return n;
}
int []dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
// dp[3] = dp[0]*dp[3] + dp[1]*dp[2] + dp[3]* dp[0]
for(int i = 2; i <= n;i++){
for(int j = 1; j <= i; j++){
dp[i] += dp[j-1]*dp[i-j];
}
}
return dp[n];
}
}