20191222——力扣动态规划_力扣 动态规划

做一个力扣单项的专栏 关于动态规划

第一个看的博文
动态规划1

动态规划的定义
动态规划实际上是一类题目的总称，并不是指某个固定的算法。动态规划的意义就是通过采用递推（或者分而治之）的策略，通过解决大问题的子问题从而解决整体的做法。动态规划的核心思想是巧妙的将问题拆分成多个子问题，通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题，从而用类似递推迭代的方法解决要求的问题。

动态规划的解题核心
动态规划的解题核心主要分为两步：

第一步：状态的定义
第二步：状态转移方程的定义
在这里，我们为了避免混淆用“状态”这个词来替代“问题”这个词。“问题”表示的含义类似：题目、要求解的内容、题干中的疑问句这样的概念。状态表示我们在求解问题之中对问题的分析转化。

**第一步：状态的定义 **

有的问题过于抽象，或者过于啰嗦干扰我们解题的思路，我们要做的就是将题干中的问题进行转化（换一种说法，含义不变）。转化成一系列同类问题的某个解的情况，比如说：

题目：求一个数列中最大连续子序列的和。

我们要将这个原问题转化为：

状态定义：Fk是第k项前的最大序列和，求F1～FN中最大值。

通过换一种表述方式，我们清晰的发现了解决问题的思路，如何求出F1～FN中的最大值是解决原问题的关键部分。上述将原问题转化成另一种表述方式的过程叫做：状态的定义。这样的状态定义给出了一种类似通解的思路，把一个原来毫无头绪的问题转换成了可以求解的问题。

第二步：状态转移方程的定义

在进行了状态的定义后，自然而然的想到去求解F1～FN中最大值。这也是状态定义的作用，让我们把一个总体的问题转化成一系列问题，而第二步：状态转移方程的定义则告诉我们如何去求解一个问题，对于上述已经转换成一系列问题我们要关注的点就在于：如何能够用前一项或者前几项的信息得到下一项，这种从最优子状态转换为下一个最优状态的思路就是动态规划的核心。
对于上面的例子题目来说，状态转移方程的定义应该是：

Fk=max{Fk-1+Ak,Ak}
Fk是前k项的和，Ak是第k项的值

仔细思考一番，我们能够得到这样的结论，对于前k个项的最大子序列和是前k-1项的最大子序列和Fk与第k项的和、或者第k项两者中较大的。如果大家还是不能理解这个原理建议用演算纸自己计算一番，这里就不过多赘述了。这种状态转移的思路就是DP的核心。

动态规划的应用场景

看过了如何去使用动态规划，那么随之而来的问题就在于：既然动态规划不是某个固定的算法，而是一种策略思路，那么什么时候应该去使用什么时候不能用呢？答案很简短：

对于一个可拆分问题中存在可以由前若干项计算当前项的问题可以由动态规划计算。

有一道例题做做看

这道题我们可以从最底层来进行分析，从第五层到自身的数字和最大值还是本身，第三层的最大值就是第三层加上第四层的和计算最大值。

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;

public class Text1 {
    public static void main(String[] args) {
        //首先创建一个二维数组，在遇到不同的数组的问题的时候用Scanner手动输入，这里按照里面要求直接创建
        int[][] dp = {{5},{8,4},{3,6,9},{7,2,9,5}};
        //声明一个变量为max为最大的和
        int max = 0;
        //创建两层循环，除去第一行遍历整个数组。
        for (int i = 1;i<4;i++){
            for(int j = 0;j<=i;j++){
                if(j == 0 ){
                    System.out.println(dp[i][j]);
                    System.out.println(i);
                    System.out.println(j);
                    dp[i][j] = dp[i-1][j] + dp[i][j];
                    System.out.println(dp[i][j]);
                }else if(j==i){
                    System.out.println(dp[i][j]);
                    System.out.println(i);
                    System.out.println(j);
                    dp[i][j] =dp[i-1][j-1]+dp[i][j];
                    System.out.println(dp[i][j]);
                }else{
                    System.out.println(dp[i][j]);
                    System.out.println(i);
                    System.out.println(j);
                    dp[i][j] =Math.max(dp[i-1][j-1],dp[i-1][j])+dp[i][j];
                    System.out.println(dp[i][j]);
                }
                max = Math.max(max,dp[i][j]);
            }
        }
        System.out.println(max);

//        for(int i = 0;i<4;i++){
//            for(int j =0;j<=i;j++){
//                System.out.println(dp[i][j]);
//            }
//        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

中间出了些问题，加上了断点测试找到问题，最后判断的时候没有加上本身，所以导致每次都少了，结果就不对了。

最后的输出结果是28没有问题。

看了一下别人的代码，

import java.util.Scanner;

public class Text2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入多少层数组");
        int n = scan.nextInt();
        long max = 0;
        int[][] dp = new int[n][n];
        dp[0][0] = scan.nextInt();

        for(int i=1;i<n;i++){
            for(int j=0;j<=i;j++){
                System.out.println("请输入"+i+j+"的数字");
                int num = scan.nextInt();
                if(j==0){
                    dp[i][j] = dp[i-1][j] + num;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j-1],dp[i - 1][j])+num;
                }
                max = Math.max(dp[i][j],max);
            }
        }
        System.out.println(max);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

一直好奇，如果dp[2] [2] 的值，应该等于dp[1][1] 与dp[1][2]的比较，但是没有后者的值该怎么比较。
后来想明白了，在数组进行初始化的时候，其他值都是0、这样就不用像我第一个代码那样再进行判断一次了。

最大子序问题

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        for(int i =1;i<nums.length;i++){
            if(nums[i-1]>0){
                nums[i] += nums[i-1];
            }
            maxSum = Math.max(nums[i],maxSum);
        }
        return maxSum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

利用动态规划来做，如果前一个数为正数，那么更新当前数，为两个数之和。