当前位置: 首页 > article >正文

数据结构和算法-动态规划(1)-认识动态规划

认识动态规划

什么是动态规划

Dynamic Programming is a method used in mathematics and computer science to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions for a wide range of problems.

动态规划(Dynamic Programming): 计算并存储小问题的解, 并将这些解组合成大问题的解。

动态规划如何工作

用一句名言开启

image-20241025112139383

Those Who Cannot Remember the Past Are Condemned(危险的) To Repeat It。

​ - 不记得过去的人注定要重蹈覆辙。

image-20241025090509359

看一个例子

计算: 1 + 1 + 1 + 1 + 1+ 1 + 1 + 1 = ?

image-20241025092515413

如果在等式左边添加1+, 即 **1 + **1 + 1 + 1 + 1 + 1+ 1 + 1 + 1=?

image-20241025092923122

如何快速的计算出答案?

image-20241025094601908

动态规划思路: 记住之前的求解,节省时间

再谈斐波拉切数列(Fibonacci )

兔子问题

image-20241025100237321

找出斐波拉切数列的数学归纳

分两种情况分析:

  • n=1,n=2 , 结果为 1
  • n>2, 结果为 n* (n-1) , n表示当前月

image-20241025101453728

构建代码(递归实现)

public int fib(int n) {
    if (n == 1 || n == 2) return 1;
    int res = fib(n - 1) + fib(n-2);
    return res;
}

分析递归实现

我们按照递归树进行分析,构建递归树模型。

image-20241025102343639

递归模型树的问题

image-20241025102854788 ·

优化方案

备忘录

自定向下的备忘录记忆,使用一个集合(数组)记录计算的结果防止重复计算。

package com.ffyc.dp;

public class Fib02 {

    public void fib(int n) {
        int[] remember = new int[n + 1]; //不使用n=0
        System.out.println(f(n, remember));
    }

    private int f(int n, int[] remember) {
        //如果remember中指定位置已经记录则直接返回,防止重复计算
        if (remember[n] != 0) {
            return remember[n];
        }
        //如果n==1,n==2则remember[1]=1, remember[2]=1
        if (n == 1 || n == 2) {
            remember[n] = 1;
        } else {
            remember[n] = f(n - 1, remember) + f(n - 2, remember);
        }
        return remember[n];
    }

    public static void main(String[] args) {
        new Fib02().fib(5);
    }
}

自低向上的动态规划
image-20241025110810355
public class Fib003 {
    public  int fib(int n){
        int[] remember = new int[n+1];

        remember[1] =1;
        remember[2] =1;

        for(int i = 3;i<=n;i++){
            remember[i] = remember[i-1]+ remember[i-2];
        }
        return remember[n];
    }

    public static void main(String[] args) {
        System.out.println(new Fib003().fib(5));
    }
}

实际上当前这个数组可以压缩为两个变量(a,b),当前的数由a,b迭代完成。–状态压缩

image-20241025111859562
public class Fib04 {

    public int fib(int n) {
        int a = 1;
        int b = 1;
        int c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    public static void main(String[] args) {
        System.out.println(new Fib04().fib(5));
    }
}

力扣斐波拉契问题

  1. [力扣LCR 126] LCR 126. 斐波那契数 - 力扣(LeetCode)
  2. [力扣 509] 509. 斐波那契数 - 力扣(LeetCode)
  3. [力扣1137] 1137. 第 N 个泰波那契数 - 力扣(LeetCode)]

http://www.kler.cn/a/373344.html

相关文章:

  • Coppelia Sim (v-REP)仿真 机器人3D相机手眼标定与实时视觉追踪 (二)
  • Atlas800昇腾服务器(型号:3000)—SwinTransformer等NPU推理【图像分类】(九)
  • solidworks学习6吊环-20241030
  • 软件测试学习笔记丨SeleniumPO模式
  • Backtrader 数据篇 02
  • C++静态成员变量需要在类外进行定义和初始化-error LNK2001:无法解析的外部符号
  • 桥接模式:解耦抽象与实现的利器
  • 【CTF】 文件包含漏洞——data伪协议 【详】
  • win11安装安卓apk原生应用,并设置网络代理
  • 基于MATLAB的地下水模拟系统开发
  • 线性可分支持向量机代码 举例说明 具体的变量数值变化
  • Django+Vue全栈开发项目入门(三)
  • Java面试经典 150 题.P88. 合并两个有序数组(001)
  • Flink CDC系列之:学习理解standalone模式
  • 商品详情接口的应用场景有那些?API接口介绍
  • Jenkins面试整理-如何安装 Jenkins?
  • 房地产网络安全:主要风险及缓解建议
  • 100种算法【Python版】第23篇——A*算法
  • 【综合算法学习】(第十篇)
  • MySQL Workbench安装教程(Windows)
  • 电力行业 | 等保测评(网络安全等级保护)工作全解
  • mysql 5.7实现组内排序(连续xx天数)
  • LeetCode Hot100 - 子串篇
  • 商场紧急预案管理:SpringBoot实现指南
  • 3. 教你用WebSocket构建一个实时聊天应用
  • Chromium 中chrome.fontSettings扩展接口定义c++