Dynamic-Programming

目录

前言 

引入 

1) Fibonacci

2) 最短路径 - Bellman-Ford

3) 不同路径-Leetcode 62

4) 0-1 背包问题

降维

5) 完全背包问题

降维

6) 零钱兑换问题-Leetcode322

降维

零钱兑换 II-Leetcode 518

7) 钢条切割问题

降维

类似题目 Leetcode-343 整数拆分

8) 最长公共子串

类似题目 Leetcode-718 最长重复子数组

9) 最长公共子序列

最长公共子序列-Leetcode 1143

两个字符串的删除操作-Leetcode 583

10) 最长上升子序列-Leetcode 300

Leetcode-96 不同的二叉搜索树

11) Catalan 数

Leetcode-22 括号生成

买票找零问题

12) 打家劫舍-Leetcode 198

13) Travelling salesman problem

---

前言 

The quote “Those who forget history are condemned to repeat it” is attributed to the American philosopher George Santayana and it can be accurately quoted as “Those who cannot remember the past are condemned to repeat it” as stated in his work, The Life of Reason: Reason in Common Sense.

 “那些忘记历史的人注定重蹈覆辙”这句话出自美国哲学家乔治·桑塔亚那之手，准确地说，这句话可以被引用为他在《理性的生活:常识中的理性》一书中所说的“那些不记得过去的人注定重蹈覆辙”。  “Those who cannot remember the past are condemned to repeat it”  这句话忘记是在哪里看到的了,但是我觉得用在动态规划这个章节,真的很合适!

引入 

 我们可以先来看一个简单的例子,我们之前用递归的方法来求解斐波那契的第n项

1) Fibonacci

public class Fibonacci {
 
    public static int fibonacci(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        int x = fibonacci(n-1);
        int y = fibonacci(n-2);
        return x+y;
    }
}

但是这个代码有缺点:

重复计算了非常多的数据.

后来我们想要用记忆法来优化: 

/**
     * <h3>使用 Memoization(记忆法, 也称备忘录) 改进</h3>
     *
     * @param n 第 n 项
     * @return 第 n 项的值
     */
    public static int fibonacci(int n) {
        int[] cache = new int[n + 1];
        Arrays.fill(cache, -1); // [-1,-1,-1,-1,-1,-1]
        cache[0] = 0;
        cache[1] = 1; // [0,1,-1,-1,-1,-1]
        return f(n, cache);
    }
 
    // f(3) => 5
    // f(4) => 9
    // f(5) => 15
    //         2*f(n+1) - 1
    private static int f(int n, int[] cache) {
        /*if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }*/
        if (cache[n] != -1) {
            return cache[n];
        }
 
        int x = f(n - 1, cache);
        int y = f(n - 2, cache);
        cache[n] = x + y; // // [0,1,?,-1,-1,-1] 存入数组
        return cache[n];
    }

动态规划也是对递归过程进行改进,只是它是从另外一种方向进行改进,避免重复计算

/**
 * 求斐波那契数列的第n项（动态规划）
 */
public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(fibonacci2(13));
    }
    /*
        要点1：
            从已知子问题的解，推导出当前问题的解
            推导过程可以表达为一个数学公式
        要点2：
            用一维或二维数组来保存之前的计算结果（可以进一步优化）
        Dynamic-Programming - 由 Bellman 提出
        动态     编程
            Programming - 在这里指用数学方法来根据子问题求解当前问题（通俗理解就是找到递推公式）
            Dynamic     - 指缓存上一步结果，根据上一步结果计算当前结果（多阶段进行）
        合在一起：
            找出递归公式，将当前问题分解成子问题，分阶段进行求解。
            求解过程中缓存子问题的解，避免重复计算。
     */
    public static int fibonacci2(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int a = 0;
        int b = 1;
        for (int i = 2; i <= n ; i++) {
            int c = b + a;
            a = b;
            b = c;
        }
        return b;
    }
 
    public static int fibonacci(int n) {
        int[] dp = new int[n + 1]; // 用来缓存结果
        if (n == 0) {
            dp[0] = 0;
            return 0;
        }
        if (n == 1) {
            dp[1] = 1;
            return 1;
        }
        for (int i = 2; i <= n ; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

2) 最短路径 - Bellman-Ford

假设要求v1-->v4的最短距离是多少?

分析:

 /*
            f(v) 用来表示从起点出发，到达 v 这个顶点的最短距离
            初始时
            f(v) = 0   当 v==起点 时
            f(v) = ∞   当 v!=起点 时

            之后
            新           旧     所有from
            f(to) = min(f(to), f(from) + from.weight)

            from 从哪来
            to   到哪去

            f(v4) = min( ∞, f(v3) + 11 ) = 20
            f(v4) = min( 20, f(v2) + 15 ) = 20

            v1  v2  v3  v4  v5  v6
            0   ∞   ∞   ∞   ∞   ∞
            0   7   9   ∞   ∞   14  第一轮
            0   7   9   20  23  11  第二轮
            0   7   9   20  20  11  第三轮
            0   7   9   20  20  11  第四轮
            0   7   9   20  20  11  第五轮

     */
 

public class BellmanFord {
    static class Edge {
        int from;
        int to;
        int weight;
 
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
 
   
    public static void main(String[] args) {
        List<Edge> edges = List.of(
                new Edge(6, 5, 9),
                new Edge(4, 5, 6),
                new Edge(1, 6, 14),
                new Edge(3, 6, 2),
                new Edge(3, 4, 11),
                new Edge(2, 4, 15),
                new Edge(1, 3, 9),
                new Edge(1, 2, 7)
        );
        int[] dp = new int[7]; // 一维数组用来缓存结果
        dp[1] = 0;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        print(dp);
        for (int i = 0; i < 5; i++) {
            for (Edge e : edges) {//更新到达v4顶点的最短路径
                if(dp[e.from] != Integer.MAX_VALUE) {
                    dp[e.to] = Integer.min(dp[e.to], dp[e.from] + e.weight);
                }
            }
        }
        print(dp);
    }
 
    static void print(int[] dp) {
        System.out.println(Arrays.stream(dp)
                .mapToObj(i -> i == Integer.MAX_VALUE ? "∞" : String.valueOf(i))
                .collect(Collectors.joining(",", "[", "]")));
    }
}

3) 不同路径-Leetcode 62

机器人要从左上角走到右下角，每次只能向右或向下，问一共有多少条不同路径？

分析，先考虑较为简单的情况

可能路径有三种情况：

• 声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/523815