动态规划

创建于

动态规划（Dynamic Programming）

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

例题1 最大子序和

https://leetcode-cn.com/problems/maximum-subarray/submissions/

给出一个数组,求连续子数组的和的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxSubArray(int[] nums) {
        if(null==nums||0==nums.length){
            return 0;
        }
        int res=nums[0];
        int d0=0;
        //初始化,最终结果为第一个元素值,第0个元素前面的连续元素最多能提供的值为0
        for(int i=0;i<nums.length;i++){//遍历每个元素
            if(d0>0){
                d0+=nums[i];//当前元素前面的连续(n个)元素能提供的值为正,那么加上当前元素,这(n+1个)元素能提供在最大值为d0＋1
            }
            else{
                d0=nums[i];//当前元素前面的连续(n个)元素能提供的值为负(或者0),那么包含当前元素能提供的最大值就是当前元素,因为负数加上当前元素总是变小的.
            }
            res=Math.max(d0,res);//保存最大值
        }
        return res;
    }
}