动态规划算法

2023-12-10数据结构与算法5 分钟141 次阅读
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面

简介

动态规划(英语:Dynamic programming,简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题,并且记录所有子问题的结果,因此动态规划方法所耗时间往往远少于朴素解法。

动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归,自底向上就是递推。

使用动态规划解决的问题有个明显的特点,一旦一个子问题的求解得到结果,以后的计算过程就不会修改它,这样的特点叫做无后效性,求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次,具有天然剪枝的功能,从而减少计算量。

力扣相关算法题:https://leetcode.cn/tag/dynamic-programming/problemset/

应用场景

例题

爬楼梯

题目:70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 1:

输入: n = 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2:

输入: n = 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示:

  • 1 <= n <= 45

解法:本题中,我们设爬 n 层楼梯有 f(n) 种方式,爬第 n 层有 f(n-1) 和 f(n-2) 种方式,而第 (n-1) 层爬上来的则有 f(n-2) 和 f(n-3) 种可能,依次类推。因此我们可以把一个大问题,不断的划分成无数个子问题来计算。

  • 当前这层是爬 1 阶上来的,则剩余 n-1 层楼梯,即有 f(n-1) 种可能。
  • 当前这层是爬 2 阶上来的,则剩余 n-2 层楼梯,即有 f(n-2) 种可能。

可以得出 f(n) 为 f(n-1) 和 f(n-2) 两种情况之和,即 f(n)=f(n−1)+f(n−2),以上递推性质为斐波那契数列。

注意:如果直接采用递归,会很多重复性的计算,最终导致计算结果超时。下边我将用两种方法解此题。
image.png

1、自顶向下法,即记忆化递归,动态规划就是利用空间换时间,极大的提高了时间效率,使用哈希表来进行记忆存储,避免重复的计算。

java 复制代码
import java.util.HashMap;
import java.util.Map;

/**
 * 70. 爬楼梯
 * https://leetcode.cn/problems/climbing-stairs/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class S_70 {
    public static void main(String[] args) {
        System.out.println(climbStairs(3));
    }

    public static int climbStairs(int n) {
        return fibonacci(n);
    }

    static Map<Integer, Integer> map = new HashMap<>();

    public static int fibonacci(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        Integer fibonacci1 = map.get(n - 1);
        if (fibonacci1 == null) {
            fibonacci1 = fibonacci(n - 1);
            map.put(n - 1, fibonacci1);
        }
        Integer fibonacci2 = map.get(n - 2);
        if (fibonacci2 == null) {
            fibonacci2 = fibonacci(n - 2);
            map.put(n - 2, fibonacci2);
        }
        return fibonacci1 + fibonacci2;
    }
}

image.png
2、自底向上,即递推,我们可以从第一层开始逐层计算每一层有多少种可能,直到第 n 层,本问题可转化为 求斐波那契数列的第 n 项。

java 复制代码
/**
 * 70. 爬楼梯
 * https://leetcode.cn/problems/climbing-stairs/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class S_70 {
    public static void main(String[] args) {
        System.out.println(climbStairs(3));
    }

    public static int climbStairs(int n) {
        // 用于存储每一层的可能性
        int[] dp = new int[n + 1];
        // 爬到第 0 层只有一种可能
        dp[0] = 1;
        // 爬到第 1 层只有一种可能
        dp[1] = 1;
        for (int i = 2; i < dp.length; i++) {
            // 上来第 n 层有两种方式:
            // 1. 从第 0 层爬 两 层楼梯上来
            // 2. 从第 1 层爬 一 层楼梯上来
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
}

image.png
3、直接使用数学公式计算,斐波那契数列公式:

Fn=1/5[(1+52)n−(1−52)n]F_n=1/\sqrt{5}[(\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n]

这里需要注意,数学中斐波那契数列是从 0 到 n ,f(0)=0,而题干中 f(0)=1,故需要算到 n+1 次。

java 复制代码
/**
 * 70. 爬楼梯
 * https://leetcode.cn/problems/climbing-stairs/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class S_70 {
    public static void main(String[] args) {
        System.out.println(climbStairs(3));
    }

    public static int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double res = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int) (res / sqrt5);
    }
}

最长回文子串

题目:5. 最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入: s = "babad"
输出: "bab"
解释: "aba" 同样是符合题意的答案。

示例 2:

输入: s = "cbbd"
输出: "bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

解法:本题中,我们可以采用动态规划,将一个最大的回文串逐一分解成求子串的回文长度,每次标记某一起始到结束位置的子串是否是回文串,用于后续一个更大串中,只需要判断左右两边的字符是否相等即可。

比如:我们判断 s="babab",我们可以先判断得到长度为 3 的子串 aba 是回文串,接着在判断是否存在长度 5 的回文串时,只需要接着判断左右下标 s[0] 与 s[4] 是否相同即可,接着收缩 s[1] 与 s[3] 之间形成的串已经被我们判断过是回文串了。所以无需再次判断。

java 复制代码
/**
 * 5. 最长回文子串
 * https://leetcode.cn/problems/longest-palindromic-substring/description/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class M_5 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));
    }

    public static String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        // 记录当前最长的回文长度
        int maxLen = 1;
        // 记录当前最长回文的起始下标
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化:所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] chars = s.toCharArray();
        // 开始递推
        // l为当前子串长度,即逐一判断是否有满足该长度的回文串
        for (int l = 2; l <= len; l++) {
            // i 表示当前串的左下标,从左边开始向右收缩
            // 判断记录在这过程中满足子串长度为 2 的回文串的起始下标和长度
            for (int i = 0; i < len; i++) {
                // 当前串的右下标 j
                int j = l + i - 1;
                // 如果右下标越界,就可以退出当前循环
                if (j > len - 1) {
                    break;
                }
                // 如果当前左右下标位置的字符不相等,则不是回文串,标记为 false
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    // 如果当前左右下标位置的字符相等
                    // 如果两个下标相邻,则这该位置的串为回文串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        // 不相邻,则判断其内部的串是否是回文串
                        // 比如: ababa,当前下标是i=0,j=4
                        // 则 接下来判断 i=1 之间的串 j= 3位置的字符串是否是回文串
                        // 即判断 str[1..3]之间的字符串
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
                if (dp[i][j] && l > maxLen) {
                    maxLen = l;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}
image.png
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句