本周的动态规划来的有些晚,上次做动态规划还是再上次(大半个月以前吧 = =),但是这周的动态规划就有意思多了
这些题不再时简单的动态规划了,首先状态方程不太好想出来,再者,在dp的基础上还要带一些tricks才能做好,比如不同路径二,他在一的基础上多了障碍物,dp的过程中要加判断,整数拆分和不同的搜索二叉树,不仅仅是简单的一层for循环就把dp数组构造出来。下面一起看一下吧。
不同路径
记得第一次面试的时候,面试官叫我手撸一题算法题,当时撸的就是这一题,当时以为是深度搜索,手写代码用的还是两层for循环,而且还贼多错误,所以我对这一题尤为记忆深刻,下面上代码
public int uniquePaths(int m, int n) {
int[][] dp = new int[m+1][n+1];//1.dp代表走到坐标dp[i][j]有多少种走法
for(int i=0; i<=m; i++){
dp[i][0] = 1;//2.dp数组的初始化,要初始化整条轴
}
for(int j=0; j<=n; j++){
dp[0][j] = 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];//3.状态方程: 现在位置 = 左边位置 + 上边位置
}
}
return dp[m-1][n-1];//下标从零开始
}
不同路径 二
这道题就是上一题的升级版了,基本的状态方程都相同,多一些判断,不多BB,上代码
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length, m = obstacleGrid[0].length;
int[][] dp = new int[n][m];
for (int i = 0; i < m; i++) {
if (obstacleGrid[0][i] == 1) break; //一旦遇到障碍,后续都到不了
dp[0][i] = 1;
}
for (int i = 0; i < n; i++) {
if (obstacleGrid[i][0] == 1) break; ////一旦遇到障碍,后续都到不了
dp[i][0] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (obstacleGrid[i][j] == 1) continue;//遇到障碍,跳过
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[n - 1][m - 1];
}
整数拆分
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
这道题哪里存在着状态转移呢,比如说给一个数:9
我们怎么知道最大的数是要拆分为三个整数:3 * 3 * 3 = 27
解释:在9之前,我们已经知道了6的最大整数拆分乘积,所以dp[9] = dp[6] * 3;
这就是状态转移所在
第二种情况:4
已知dp[2] = 1 * 1 = 1;//初始状态
最大值等于:2 * 2 = 4 dp[4] = 2 * 2 而不是 dp[4] = dp[2] * 2
上代码:
public int integerBreak(int n) {
int[] dp = new int[n+1];
dp[2]=1;
for(int i=3; i<=n; i++){
for(int j=1; j<=i; j++){
dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));//取遍历过程中最大的dp[i],所以还需要和dp[i]比较一下
}
}
return dp[n];
}
不同的搜索二叉树
这道题要看官方的题解了,我用文字也很难描述,我就简单解释一下
- dp[n]代表有n个节点的二叉搜索树的数量
- 初始化:没有节点和一个节点时只有一种
- 状态方程 : 看下面的注解
public int numTrees(int n) {
//初始化 dp 数组
int[] dp = new int[n + 1];
//初始化0个节点和1个节点的情况
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
//对于第i个节点,需要考虑1作为根节点直到i作为根节点的情况,所以需要累加
//一共i个节点,对于根节点j时,左子树的节点个数为j-1,右子树的节点个数为i-j
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
至此,动态规划的第二周做的题目就记录完了,接下来动态规划要上强度了,前面只能算是热身。