乐趣区

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

jiezi

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

动静布局（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/…

退出移动版