关于java:动态规划初步理解

本篇次要是对援用文的了解、记录,对动静布局有一个初步的了解。

动静布局(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。

解决问题的前提是做好逻辑布局,白描出思路,而后再讲思路转换为代码实现,进而对代码进行优化,应用现成的已有的语法更疾速高效的解决问题。

援用文先解说了解决动静布局问题的思路,后举例说明,跟学了前三个例子。

动静布局,无非就是利用历史记录,来防止咱们的反复计算。而这些历史记录,咱们得须要一些变量来保留,个别是用一维数组或者二维数组来保留。
第一步骤:定义数组元素的含意;
第二步骤:找出数组元素之间的关系式;
第三步骤:找出初始值;

了解与解读:
第一步骤,将问题拆解为一系列的子问题,并明确子问题的含意,逐个求解子问题,进而得解。
第二步骤,了解子问题之间的互相关系,并将这种关系转换为一个公式;
第三步骤,子问题公式推导到不能推导的最初,必然有可能间接获取的值,这就是初始值,在进行推导之前要给定给出初始值,整个推导过程最初能力有解。

援用文中的前三个例子已练习,上面给出本人的例子(尽管也参考了官网题解):


/**
 * 53. 最大子数组和
 * 给你一个整数数组 nums ,请你找出一个具备最大和的间断子数组(子数组起码蕴含一个元素),返回其最大和。
 * 子数组 是数组中的一个间断局部。
 * 示例 1:
 * 输出:nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输入:6
 * 解释:间断子数组[4,-1,2,1] 的和最大,为6 。
 * 起源:力扣(LeetCode)
 * 链接:<a href="https://leetcode.cn/problems/maximum-subarray">...</a>
 * 著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
 */
public class MaximumSubarray {


    public static int maxSubArray1(int[] nums) {
        //1、定义一个数组dp:dp[i]为以第i个元素为结尾的间断子数组的最大和, 最初求出dp中max值即为后果值
        int[] dp = new int[nums.length];

        //2、元素间的关系:dp[i] = max(dp[i-1]+nums[i], nums[i])
        //3、找出初始值
        int maxSubArrayCount = nums[0];
        dp[0] = nums[0];
        for(int i=1; i<nums.length; i++){
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            maxSubArrayCount = Math.max(dp[i], maxSubArrayCount);
        }

        return maxSubArrayCount;
    }

    public static int maxSubArray2(int[] nums) {
        //1、定义一个数组dp:dp[i]为以第i个元素为结尾的间断子数组的最大和, 最初求出dp中max值即为后果值
        //int[] dp = new int[nums.length];

        //2、元素间的关系:dp[i] = max(dp[i-1]+nums[i], nums[i])
        //3、找出初始值
        int maxSubArrayCount = nums[0];
        int dp = 0;
        for (int num : nums) {
            dp = Math.max(dp + num, num);
            maxSubArrayCount = Math.max(dp, maxSubArrayCount);
        }

        return maxSubArrayCount;
    }
}

援用
辞别动静布局,连刷 40 道题,我总结了这些套路,看不懂你打我(万字长文)https://juejin.cn/post/684490…
动静布局百度百科 https://baike.baidu.com/item/…

【腾讯云】云产品限时秒杀,爆款1核2G云服务器,首年50元

阿里云限时活动-2核2G-5M带宽-60G SSD-1000G月流量 ,特惠价99元/年(原价1234.2元/年,可以直接买3年),速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据