数据结构与算法—算法篇之动态规划(一)

✨数据结构与算法—算法篇之动态规划(一)

作者介绍:

🎓作者:偷偷敲代码的青花瓷🐱‍🚀
👀作者的Gitee:代码仓库
📌系列文章推荐:
🤳JAVA刷题特辑🤳 第一章 JAVA之牛客网刷题📖笔记 【✨点进来花两把游戏的时间学习晚上睡觉都踏实了】
✨✨我和大家一样都是热爱编程✨,很高兴能在此和大家分享知识,希望在分享知识的同时,能和大家一起共同进步,取得好成绩,拿到好offer🐱‍🚀JAVA刷题特辑将持续更新🐱‍🚀,如果有错误❌,欢迎指正呀✔,如果觉得收货满满,可以点点赞👍,支持一下哟~~😁

目录

文章目录

• 什么是动态规划
• • 动态规划本质
  • 动态规划的特点
  • 动态规划的解题思路:
  • • 动态规划问题一般从哪几个角度考虑
    • 什么样的问题可以考虑使用动态规划解决呢？
    • 解题步骤
• 例题(详细剖析)
• • • 斐波那契数列
    • 连续子数组的最大和
    • 公共子串计算
    • 字符串分割(Word Break)
    • 字符串通配符
• 总结

什么是动态规划

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。(通俗的来讲就是 大事化小,小事化无)

动态规划本质

动态规划的本质，是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)

动态规划的特点

1.把原问题 分解成了几个相似的子问题
2.所有的 子问题都只需要解决一次
3.存储子问题的解

动态规划的解题思路:

动态规划问题一般从哪几个角度考虑

1.状态定义
2.状态间的转译方程定义
3.状态的初始化
4.返回结果
状态定义的要求:一定要形成递推关系

一句话概括:三特点四要素两本质

什么样的问题可以考虑使用动态规划解决呢？

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

比如:

比如一些求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景。
通俗的来说就是遇到说求:最大值/最小值,可不可行,是不是,方案个数

解题步骤

1.确认状态
2.转移方程
3.初始条件
4.执行顺序

话不多说,跟紧步伐,我们边看列题边学习

例题(详细剖析)

斐波那契数列

题目:

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1     F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

来源:牛客剑指offer

思路:

代码实现:

public class Solution {
    public int Fibonacci(int n) {
        //创建一个数组保存中间状态
        int[] arr = new int[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        for(int i = 2;i <= n; i ++) {
            arr[i] = arr[i-1] + arr[i -2];
        }
        return arr[n];
    }
}

连续子数组的最大和

题目描述:

给定一个数组 array[1, 4, -5, 9, 8, 3, -6]，在这个数字中有多个子数组，子数组和最大的应该是：[9, 8, 3]，输出20，再比如数组为[1, -2, 3, 10, -4, 7, 2, -5]，和最大的子数组为[3, 10, -4, 7, 2]，输出18。

思路:

状态方程式： max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] )
上面式子的意义是：我们从头开始遍历数组，遍历到数组元素 arr[ i ] 时，连续的最大的和 可能为 max( dp[ i -1 ] ) + arr[ i ] ，也可能为 arr[ i ] ，做比较即可得出哪个更大，取最大值。时间复杂度为 n。
dp[i] 就是以数组下标为 i 的数做为结尾的最大子序列和，注意是以 i 为结尾，比如说现在有一个数组{6,-3,-2,7,-15,1,2,2}，dp[2]就是以-2为结尾的，那么显然dp[2]的最大值就是1咯

代码:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
            //把元素放入数组中
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = s.nextInt();
        }
        System.out.println(func(arr));

    }
    public static int func(int[] arr) {
        if(arr.length == 0) {
            return 0;
        }
        int sum = arr[0];//临时最大值
        int maxSum = arr[0];//比较之后的最大值
        for (int i = 1; i < arr.length ; i++) {
            sum = Math.max(sum+arr[i],arr[i]);
            maxSum = Math.max(sum,maxSum);
        }
        return maxSum;

    }
}

公共子串计算

题目描述:

给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
数据范围：字符串长度：1\le s\le 150\1≤s≤150
进阶：时间复杂度：O(n^3)\O(n 3 ) ，空间复杂度：O(n)\O(n)

输入描述:输入两个只包含小写字母的字符串
输出描述:输出一个整数，代表最大公共子串的长度

输入:
asdfas
werasdfaswer
输出:
6

思路:

牛客OJ链接

代码:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            System.out.println(GetMaxLen(str1,str2));
        }
    }
    
    public static int GetMaxLen(String str1,String str2) {
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        int len1= arr1.length;
        int len2 = arr2.length;
        int[][] maxSubLen = new int[len1+1][len2+1];
        int maxLen = 0;
        for(int i = 1;i <= len1;i++) {
            
            for(int j = 1;j <= len2;j++) {
                if(arr1[i -1] == arr2[j -1]) {
                    maxSubLen[i][j] = maxSubLen[i-1][j-1] + 1;
                }
                if(maxLen < maxSubLen[i][j]) {
                    maxLen = maxSubLen[i][j];
                }
            }
        }
        return maxLen;      
     }
}

字符串分割(Word Break)

题目描述:

给定一个字符串和一个词典dict，确定s是否可以根据词典中的词分成一个或多个单词。
比如，给定
s = "leetcode"
dict = ["leet", "code"]
返回true，因为”leetcode”可以被分成”leet code”

思路:

状态F(i):
子状态：前1，2，3，…,n个字符能否根据词典中的词被成功分词F(i): 前i个字符能否根据词典中的词被成功分词
状态递推：
F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR false在j小于i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典中找到，则F(i)为true
初始值：
对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单的例子进行验证 F(0) = true
返回结果：F(n)

牛客OJ链接

代码:

import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        // boolean 数组
        boolean[] canBreak = new boolean[s.length()+1];
        // 初始化
        canBreak[0] = true;
        
        for(int i = 1;i <= s.length();i++) {
            
            //j < i && F(j) && [j+1,i] 
            for(int j = 0;j < i;j++) {
            //subString 左闭右开
                if(canBreak[j] && dict.contains(s.substring(j,i))) {
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[s.length()];
        
    }
}

字符串通配符

题目描述:

要求：
实现如下2个通配符：
*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符
注意：匹配时不区分大小写。
输入：
通配符表达式；
一组字符串。
输入描述：
先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
输出描述：
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

示例:

输入:te?t*.*
     txt12.xls
输出:false

输入:pq
     pppq
输出:false

输入:?*Bc*?
     abcd
输出:true

思路:

解决方法是根据题意设定初值、填表，然后找出规律升级为递推式。

可以看到分成三种情况：
分别是“?”,它能匹配任意一个字符，所以如果它的上一个字符串匹配成功，则它一定能匹配成功
第二种是“*”，它可以匹配0个或者多个，从表上的规律可以看出他匹配成功需要满足的规律是：上面或者左边的成功就是true。
第三种是普通字符，从表上得出，它匹配成功的条件是：它与在待匹配字符串中对应位置相同的字符相同，并且上一个匹配成功那么它可以匹配成功。
最后都匹配完`，那么右下角就是最终的情况。

牛客链接

代码:

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextLine()){
            String t=sc.nextLine();
            String s=sc.nextLine();
            System.out.println(match(t,s));
        }
    }
    public static boolean match(String t,String s){
        char[] ct=t.toCharArray();
        char[] cs=s.toCharArray();
        int lt=ct.length;
        int ls=cs.length;
        boolean[][] dp=new boolean[ls+1][lt+1];
        dp[0][0]=true;
        for(int i=0;i<=ls;i++){
            for(int j=1;j<=lt;j++){
                if(ct[j-1]=='*'){
                    if(i==0){
                       dp[i][j]=dp[i][j-1];
                    }else{
                        if(cs[i-1]=='.' || (cs[i-1]>='0'&&cs[i-1]<='9') ||
                          (cs[i-1]>='a'&&cs[i-1]<='z') ||(cs[i-1]>='A'&&cs[i-1]<='Z')
                       ) {
                            dp[i][j]=dp[i-1][j] || dp[i][j-1];
                    }

                }
                    
            }else{
                    if(i>0 && defs(ct[j-1],cs[i-1])){
                        dp[i][j]=dp[i-1][j-1];
                  }
           }
        }           
    }
        return  dp[ls][lt];
}
    public static boolean defs(char t,char s){
        if(t=='?') return true;
        if(t>='a'&&t<='z'){
            t=(char)(t-'a'+'A');

        }
        if(s>='a'&&s<='z'){
            s=(char)(s-'a'+'A');
        }
        return s == t;
    }
}
    

总结

“种一颗树最好的是十年前,其次就是现在”
所以,
“让我们一起努力吧,去奔赴更高更远的山海”

如果有错误❌,欢迎指正哟😋

🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉