网站做微信接口吗,网站开发如何无感更新,如何留住网站用户,网红营销方式本次文档也是对动态规划的 再认识 。 之前写过一些文章#xff0c;在处理动态规划问题的时候依据的思路是 #xff1a;暴力搜索-加缓存-动态规划。相关文章有#xff1a;算法八——动态规划#xff0c;动态规划——0-1背包问题#xff0c;动态规划——矩阵中的最短…本次文档也是对动态规划的 再认识 。 之前写过一些文章在处理动态规划问题的时候依据的思路是 暴力搜索-加缓存-动态规划。相关文章有算法八——动态规划动态规划——0-1背包问题动态规划——矩阵中的最短路径长度等等。 最近在看问题的时候发现只要能明白暴力搜索是怎么搜索的跟哪些条件有关系不经过前面2个步骤也能写出动态规划方程。大家知道动态规划方程出来了基本上问题就解决了。写下文章记录一下 。 如果看不出和哪些条件有关系或者找不到动态转换关系还是要依据步骤一步一步来。
1 53. Maximum Subarray
输入int数组有正有负 输出找到所有子数组的和返回其中最大的。 规则子数组是一个连续的数组至少包含一个元素。 例如 Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum 6.
分析对于任意一个元素nums[i]可以开启一个子序列{nums[i]}也可以追加在前一个数字子序列的后面{…nums[i-1],nums[i]}。 对于开启一个子序列的情况 子数组和nums[i]。 对于追加的情况目标是要求子数组和所以只要之前以nums[i-1]为结尾的子数组的和nums[i]即可。假设dp[i]以nums[i]为结尾的子数组的最大的和。 最后结果在所有dp元素中查找最大值。 dp[i] Math.max(nums[i],nums[idp[i-1]]) 动归特征与前一个元素相关与以前一个元素为结尾的子数组最大和相关。 之后就是写代码了。
class Solution {public int maxSubArray(int[] nums) {int n nums.length;int[] dp new int[n];dp[0] nums[0];int max dp[0];for(int i1;in;i){dp[i] Math.max(nums[i],dp[i-1]nums[i]);max Math.max(max,dp[i]);}return max;}
}进一步空间优化可以自己思考。
2 121. Best Time to Buy and Sell Stock
输入int数组表示每天的股价。 输出最大的盈利 规则只可以买一次卖一次。只能先买后卖。 例子 Input: [7,1,5,3,6,4] Output: 5 Explanation: 在价格为1的时候买入在价格为6的时候卖出。 分析只能买卖一次先买后卖说明是要找max(price[j]−price[i]),jimax(price[j]-price[i]),jimax(price[j]−price[i]),ji。对于每一个j只要找到min(price[i]),i0,1...j−1min(price[i]),i0,1...j-1min(price[i]),i0,1...j−1即可。
class Solution {public int maxProfit(int[] prices) {int maxProfit 0;int minPrice Integer.MAX_VALUE;for(int i0;iprices.length;i){minPrice Math.min(minPrice,prices[i]);maxProfit Math.max(maxProfit,prices[i]-minPrice);}return maxProfit;}}
