动态规划（dp）

递归与动态规划

动态规划是自底向上，递归树是自顶向下。

自顶向下：从一个规模较大的问题向下逐渐分解。如斐波那契问题，计算 f(20)，逐步分解到f(1)、f(2)，然后返回结果。

1
2
3
4
5
6
7
int Fibonacci(size_t n){
    if(n==1||n==2){
        return n;
    }
    return Fibonacci(n-1)+Fibonacci(n-2);
}
//递归虽然代码优雅，但是数值过大可能会算不出来。

自底向上：从最底下、最简单的问题开始往上推，也就是动态规划的思想，通过循环迭代得到结果。

1
2
3
4
5
6
7
8
9
//利用动态规划计算斐波那契数列
int Fibonacci(int n){
    vector<int> dp(N+1,0);//dp数组初始化
    dp[1]=dp[2]=1;
    for(int i=3;i<=N;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[N];
}

动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

问题是否能用动态规划解决的是这些”小问题“会不会被被重复调用。

能用动态规划解决的问题

1、问题的答案依赖于问题的规模，也就是问题的所有答案构成了一个数列。

2、大规模问题的答案可以由小规模问题的答案递推得到，也就是[公式]的值可以由[公式]中的个别求得。

应用动态规划

1、建立状态转移方程

2、缓存和复用以往结果

3、按顺序从小往大算

经典题型

连续子数组的最大和

问题陈述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例：

1
2
3
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路分析

连续子数组，和最大，我们可以用dp的思想来解决此类问题，

走一遍nums数组元素，初始值为dp[0]=-2,从dp[1]开始判断，若之前和大于0，则加上；若小于0，则dp[i]=nums[i]。

并定义res存储最大值，res初始化为nums[0]，并与每次的dp[i]比较取最大值。

通过上述分析：即知转移条件为：**dp[i]=nums[i] 当dp[i-1]<0; **

​ dp[i]=nums[i]+dp[i-1] 当dp[i-1]>0。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    //此处代码与上思想一致，只是dp[]覆盖了原来的nums数组。即新的nums数组即为dp。
    public int maxSubArray(int[] nums) {
        int res=nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i-1]<0){
                nums[i]=nums[i];
            }else{
                nums[i]+=nums[i-1];
            } 
            res=Math.max(res,nums[i]);
        }
        return res;

    }
}