算法(三) 动态规划
动态规划
- 利用历史记录(子问题的结果)来避免重复计算。
- 历史记录需要用一些变量来保存，一维数组和二维数组比较多。
俺的做题步骤
- 明确dp数组的含义，也就是对历史记录的定义。
- 找出数组元素间的关系，如dp[n] = dp[n-1] + dp[n-2]。
- 找出初始值，因为关系式需要一个初始值进行结束。但是一定要找全！
例题
1，买卖股票最佳时间(智商题，动态规划)
来自 LeetCode121
解法
1，智商题
- 本题除了要求大数在小数后面，没有其他要求（如长度，时间等都没有要求）。
- 所以可以得出，只需要得到前面最小值和后面的最大值，双方差值一定为最大利润。
- 且因为被限制大数在小数后面的问题，所以该方法不会出现遗漏。（出现比原定min更小的数字时，如果后面有能使max更大的数，取原来的min利润一定会小于新取的min利润）
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
int min = Integer.MAX_VALUE;
for(int now : prices){
if(now<min)
min = now;
else if(now - min > max)
max = now - min;
}
return max;
}
}2，动态规划
- 俺的粗糙解法
class Solution {
public int maxProfit(int[] prices) {
int min;
int[] dp = new int[prices.length];
if(prices.length==1)
return 0;
dp[0]=0;
if(prices[1]>prices[0]){
dp[1] = prices[1] - prices[0];
min = prices[0];
}
else{
dp[1] = 0;
min = prices[1];
}
for(int i = 2;i<prices.length;i++){
if(prices[i]<min)
min = prices[i];
dp[i] = Math.max(dp[i-1],prices[i]-min);
}
return dp[prices.length-1];
}
}很粗糙，空间复杂度O(m*n)，太高。需要进行动态规划的优化算法。
- 大佬解法
class Solution {
public int maxProfit(int[] prices) {
if(prices.length <= 1)
return 0;
int min = prices[0], max = 0;
for(int i = 1; i < prices.length; i++) {
max = Math.max(max, prices[i] - min);
min = Math.min(min, prices[i]);
}
return max;
}
}理解（不保证正确）
无
2，不同路径
来自LeetCode62
解法
1，俺的动态规划
class Solution {
public int uniquePaths(int m, int n) {
int[][] 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];
}
}空间复杂度为m*n，需要进一步优化。
2，动态规划优化后
待补充。
理解
- 务必先确定dp数组的定义和初始值要哪些！！！！
3,最小路径和（不同路径的不同方向）
来自 LeetCode 64
解法
1，俺的动态规划
class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
dp[0][0] = grid[0][0];
for(int i = 1;i<grid[0].length;i++){
dp[0][i]=dp[0][i-1]+grid[0][i];
}
for(int j = 1;j<grid.length;j++){
dp[j][0] = dp[j-1][0] + grid[j][0];
}
for(int i = 1;i<grid.length;i++){
for(int j = 1;j<grid[0].length;j++){
dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + grid[i][j];
}
}
return dp[grid.length-1][grid[0].length-1];
}
}空间复杂度0(m*n)，可以优化。
2，动态规划优化。
学了再搞。
理解
无。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-08-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
