这周的重心在算法题上，今天刷了三道算法题，基本都是最优解
-
不同路径
题目链接：https://leetcode.cn/problems/unique-paths/
代码：
class Solution {
public int[][] dp;
public int uniquePaths(int m, int n) {
dp=new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0]=1;
}
for (int i = 0; i < n; i++) {
dp[0][i]=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];
}
}
-
不同路径 II
题目链接：https://leetcode.cn/problems/unique-paths-ii/
代码：
class Solution {
public int[][] dp;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int height=obstacleGrid.length;
int length=obstacleGrid[0].length;
dp=new int[height][length];
if(obstacleGrid[0][0]==0){
dp[0][0]=1;
}
for (int i = 1; i < height; i++) {
if (obstacleGrid[i][0]==1){
dp[i][0]=0;
}else {
dp[i][0]=dp[i-1][0];
}
}
for (int i = 1; i < length; i++) {
if (obstacleGrid[0][i]==1){
dp[0][i]=0;
}else {
dp[0][i]=dp[0][i-1];
}
}
for (int i = 1; i < height; i++) {
for (int j = 1; j < length; 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][length-1];
}
}
-
整数拆分
题目链接：https://leetcode.cn/problems/integer-break/
代码：
class Solution {
public int size;
public int maxValue;
public int avg;
public int integerBreak(int n) {
size=2;
maxValue=1;
avg=1;
for (int i = 2; i < n; i++) {
int newAvg=(i+1)/(size+1);
int bigNumberSize=(i+1)-newAvg*(size+1);
int smallNumberSize=size+1-bigNumberSize;
int value1=maxValue*(avg+1)/avg;
int value2= (int) (Math.pow(newAvg,smallNumberSize)*Math.pow((newAvg+1),bigNumberSize));
if (value1>value2){
maxValue=value1;
avg=(i+1)/size;
}else {
maxValue=value2;
size++;
avg=newAvg;
}
}
return maxValue;
}
}
