杭州互助盘网站开发,深圳市宝安区石岩街道,长沙推广优化公司,wordpress新用户提醒#x1f525; 个人主页: 黑洞晓威 #x1f600;你不必等到非常厉害#xff0c;才敢开始#xff0c;你需要开始#xff0c;才会变的非常厉害 343. 整数拆分
给定一个正整数 n #xff0c;将其拆分为 k 个 正整数 的和#xff08; k 2 #xff09;#xff0c;并使… 个人主页: 黑洞晓威 你不必等到非常厉害才敢开始你需要开始才会变的非常厉害 343. 整数拆分
给定一个正整数 n 将其拆分为 k 个 正整数 的和 k 2 并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
解题思路
这个问题可以使用动态规划来解决。我们定义一个数组 dp其中 dp[i] 表示将正整数 i 拆分后可以获得的最大乘积。
首先我们初始化 dp[1] 1因为任何数拆分成两个数的乘积最小值为 1 * 1 1。
然后我们从正整数 2 开始依次计算 dp 数组的值。对于每个正整数 i我们通过迭代 jj 的范围是从 1 到 i - 1来计算 dp[i]。对于每个 j我们计算两种情况下的最大值
j * (i - j)将 i 拆分成 j 和 i - j 两个数相乘的结果。j * dp[i - j]将 i 拆分成 j 和 dp[i - j] 两个数相乘的结果。
代码实现
class Solution {public int integerBreak(int n) {int[] dp new int[n 1];dp[1] 1; // 初始化 dp[1]for (int i 2; 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]));}}return dp[n];}
}
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径
网格中的障碍物和空位置分别用 1 和 0 来表示
解题思路
我们可以定义一个二维数组 dp其中 dp[i][j] 表示从起始点到达网格的位置 (i, j) 的不同路径数。根据题目要求如果某个位置有障碍物那么该位置的路径数为 0。
接下来我们可以根据动态规划的状态转移方程来计算 dp 数组。状态转移方程如下
如果当前位置 (i, j) 是障碍物obstacleGrid[i][j] 1那么 dp[i][j] 0否则dp[i][j] dp[i-1][j] dp[i][j-1]即当前位置的路径数等于上方和左方位置的路径数之和。
最终dp[m-1][n-1] 即为从起始点到达右下角的不同路径数。
代码实现
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] dp new int[m][n];// 初始化起始点dp[0][0] obstacleGrid[0][0] 1 ? 0 : 1;// 初始化第一列for (int i 1; i m; i) {dp[i][0] obstacleGrid[i][0] 1 ? 0 : dp[i-1][0];}// 初始化第一行for (int j 1; j n; j) {dp[0][j] obstacleGrid[0][j] 1 ? 0 : dp[0][j-1];}// 计算其余位置的路径数for (int i 1; i m; i) {for (int j 1; j n; j) {dp[i][j] obstacleGrid[i][j] 1 ? 0 : dp[i-1][j] dp[i][j-1];}}return dp[m-1][n-1];}
}
