您现在的位置是:首页 >技术交流 >动态规划问题网站首页技术交流
动态规划问题
简介动态规划问题
动态规划:记录前一部分的最优解,与后文进行比较
经典dp问题 力扣62:不同路径https://leetcode.cn/problems/unique-paths/description/
先初始化第一行第一列路径只有一条,然后dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
public int uniquePaths(int m, int n) {
int dp[][] = new int[m][n];
for(int i = 0; i < n; i++) dp[0][i] = 1;
for(int i = 0; i < m; i++) dp[i][0] = 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];
}
}
力扣118:杨辉三角https://leetcode.cn/problems/pascals-triangle/description/
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
int dp[][] = new int[numRows][numRows];
for(int i = 0; i < numRows; i++){
List<Integer> list = new ArrayList<>();
for(int j = 0; j <= i; j++){
if(j == 0){
dp[i][j] = 1;
list.add(1);
}else{
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
list.add(dp[i][j]);
}
}
res.add(list);
}
return res;
}
分治法:大事化小,逐一解决
力扣53 最大子数和https://leetcode-cn.com/problems/maximum-subarray/submissions/
public int maxSubArray(int[] nums) {
int maxSum = nums[0], thisSum = 0;
for(int num : nums){
thisSum += num;
if(thisSum > maxSum) maxSum = thisSum;
if(thisSum < 0) thisSum = 0;
}
return maxSum;
}
dp:力扣47 礼物的最大值https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
public int maxValue(int[][] grid) {
int n = grid.length, m = grid[0].length;
int dp[][] = new int[n+1][m+1];
for(int i = 0; i < n; i++){
for(int j = 0;j < m; j++){
dp[i+1][j+1] = Math.max(dp[i][j+1] + grid[i][j], dp[i+1][j] + grid[i][j]);
}
}
return dp[n][m];
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。