程序员经验分享-hwhale

动态规划（Dynamic Programming）入门

2023-10-27

前言

算法实验课的题目是一道关于动态规划（Dynamic Programming）的题目，正好借这个机会，学习一下动态规划（Dynamic Programming）。

动态规划简单介绍

动态规划（Dynamic Programming，简称DP）的基本想法就是将原问题转化为一系列相互联系的子问题，然后通过逐层递推来求得最后的解。

动态规划快速而高效解决问题的关键就是利用历史记录，来避免重复计算。

动态规划的题目特点

一般来说，我们面对各式各样的算法题，可能会有许多不同的想法，有些题目适合动态规划，有些题目可能不适合动态规划，那么哪些题目适合动态规划呢？

当我们看见如下三种类型的题目时，可以首先考虑一下，DP是否可以成为解决这道题的方法（当然，不一定是最优的算法）

  • 计数型算法题
    1. 有多少种方式走到右下角
    2. 有多少种方式选出k个数，使其和为sum
  • 求最大最小值型算法题
    1. 从左上角走到右下角路径的最大数字和
    2. 最长上升子序列长度
  • 求存在性算法题
    1. 取石子游戏，先手是否必胜
    2. 能不能选出k个数使得和为sum

例题分析

对于以上三种题型，我们举三个简单的题目来总结出动态规划问题的解题思路。

例题一：Coin Change(LeetCode 332)

题目描述：

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
您将获得一个整数数组，表示不同面额的硬币，以及一个整数金额，表示总金额。
返回您需要的最少数量的硬币，以弥补该金额。如果这些硬币的任何组合都无法弥补这一数额，则返回-1。
你可以假设每种硬币的数量是无限的。

举例分析一下

我们有三种硬币，面值分别为2元、5元和7元，且假设每种硬币有无限多。
买一本书需要27元。
如何用最少的硬币组合正好付清？

分析：
拿到问题的时候，我首先想到的是尽可能用大面值
即7+7+7=21
21+5=26
没有得到27

那我们改变一下策略，尽量使用大面值，最后可以使用一种硬币付清就行
所以我们得到了
21+2+2+2=27
所以得到答案为6，但是这个答案是错误的

正确答案是5，7+5+5+5+5=27

为什么会出现这种情况呢？换句话说，第一种算法有什么问题呢？

对于每一种正确的算法，我们应该可以通过数学证明出该方法是正确的，但实际上，我们并不能证明这种算法是正确的，贪心只是局部最优，但对于整体而言，它不一定是最优的。

那么利用动态规划该如何解决这个问题呢？

我们运用DP解决问题时，只需要把握以下四个部分就行：

  • 确定状态
  • 转移方程
  • 初始条件和边界条件
  • 计算顺序

确定状态

解动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j] 代表什么，就像数学中，x，y，z表示什么。

确定状态需要两步

  1. 最后一步

    对于这个问题，虽然我们还不知道最优策略是什么，但是我们知道最优策略一定是k枚硬币，a1，a2…ak相加得到27

    所以一定有最后一枚硬币ak

    除去ak，前面的硬币加起来就是27-ak
    在这里插入图片描述
    事实上，我们并不关心前面k-1枚硬币是怎么组成27-ak的，它可以有很多种方式，但肯定至少有一种，而且我们可以知道，前面k-1枚硬币组成27-ak的策略一定是最优的。

    也就是说，我们的最后一步就是（27-ak）+ak=27

  2. 子问题

    原来的问题是最少用多少枚硬币组成27
    现在的问题变成了最少用多少枚硬币组成27-ak

    我们把这种问题一样，规模变小的问题称为原问题的子问题。

    为了简化表达，我们设状态f[X]=最少用多少枚硬币组成X

    等等，此刻，我们似乎还不知道ak是多少
    但是，毫无疑问，ak只能是2，5，7三个数的其中一个
    如果ak=2,那么f[27]=f[27-2]+1（加上最后一枚硬币）
    如果ak=5,那么f[27]=f[27-5]+1（加上最后一枚硬币）
    如果ak=7,那么f[27]=f[27-7]+1（加上最后一枚硬币）

    为了满足硬币最少的需求，我们就得到了：
    f[27]=min{f[27-2]+1，f[27-5]+1，f[27-7]+1}

写到这里可能就有很多小伙伴们会直呼这不就是递归吗？

那我们就用递归来看看，递归伪代码如下：
在这里插入图片描述
毫无疑问，当X=0时，拼成0的方法有0种

那么为什么定义初始值为正无穷呢？
关于这一点，我们会在DP的第三步：初始条件和边界条件中具体讲解。

这个方法有什么问题？
理论上，这个方法可以解决问题，但是递归有如下的问题：
在这里插入图片描述
我们可以看到，每一次递归的时候，都会进行大量的重复计算，这样程序的效率是非常低下的，那么如何避免？

我们来看一看本文的主角DP是如何做的。

转移方程

DP的一个重点就是转移方程，将原问题转移到子问题。
我们设f[X]=最少用多少枚硬币组成X
那么转移方程就是：f[X]=min{f[X-2]+1，f[X-5]+1，f[X-7]+1}

初始条件和边界条件

对于f[X]=min{f[X-2]+1，f[X-5]+1，f[X-7]+1} 这个转移方程
我们有两个问题：

  1. X-2，X-5，X-7小于0怎么办？什么时候停下来
  2. 什么时候停下来？

如果不能拼出Y，我们就定义f[Y]为正无穷
例如f[-1]、f[-2]=正无穷
当然，对于数组下标，我们不可能让它等于负数，那么我们只需要在要用到f[负数]的时候就让它返回正无穷就行

同时我们也可以得到f[1]=min{f[1-2]+1，f[1-5]+1，f[1-7]+1}=正无穷，表示拼不出1

同时我们也可以得到初始条件f[0]=0

什么时候要定义初始化呢？
对于f[0],我们通过转移方程求解时得到的是正无穷，而我们明明知道f[0]的值为0，那么我们就可以手动定义为0

计算顺序

最少用多少枚硬币组成X：f[X]=min{f[X-2]+1，f[X-5]+1，f[X-7]+1}

初始化条件：f[0]=0

那么计算顺序应该怎么安排呢？

我们知道想要求f[8]，我们就必须知道f[6]，f[3]，f[1]，所以什么进行从小到大的顺序进行计算。

与递归相比：
DP每一步尝试3种硬币，一共尝试27步
所以，算法时间复杂度为：27*3，远小于递归的算法时间复杂度

小结与代码实现

求最值型动态规划

DP四个部分：

  1. 确定状态：最后一步和子问题
  2. 转移方程
  3. 确定初始条件和边界情况
  4. 确定计算顺序

消除冗余，加速计算

OK，我们现在代码实现一下这道题（LeetCode 332 Coin Change)

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] f=new int[amount+1];
        int n=coins.length;
        
        //初始条件
        f[0]=0;
        
        for(int i=1;i<=amount;++i){
            f[i]=Integer.MAX_VALUE;
            //最后一步
            for(int j=0;j<n;++j){
                if(i>=coins[j]&&f[i-coins[j]]!=Integer.MAX_VALUE){
                     f[i]=Math.min(f[i-coins[j]]+1,f[i]);//转移方程
                }
            }
        }
        if(f[amount]==Integer.MAX_VALUE){
            f[amount]=-1;
        }
        return f[amount];
    }
}
}

例题二：Unique Paths(LeetCode 62)

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
机器人位于m x n网格的左上角（下图中标记为“开始”）。
机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角（下图中标记为“Finish”）。
有多少种可能的唯一路径？
在这里插入图片描述

确定状态

  1. 最后一步
    在这里插入图片描述
    如果右下角finsh为（m-1,n-1)
    那么前一步，机器人一定在（m-2,n-1)或者（m-1,n-2)

  2. 子问题
    如果机器人有X种方式走到（m-2,n-1)，有Y种方式走到（m-1,n-2)，那么机器人有X+Y种方式走到finsh

    现在问题就转换为机器人有多少种方式走到（m-2,n-1和（m-1,n-2)

状态：设f[i][j]为机器人有多少种方式走到（i，j）

转移方程

对任意一个格子：f[i][j]=f[i-1][j]+f[i][j-1]

初始条件和边界情况

初始条件：f[0][0]=1
边界情况：当i=0或者j=0时，f[i][j]=1

计算顺序

f[0][0]=1
计算第0行，从左往右
计算第1行，从左往右
…
计算第m-1行，从左往右

小结与代码实现

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f=new int[m][n];
        for(int i=0;i<m;++i){//从上到下
            for(int j=0;j<n;++j){//从左到右
                if(i==0||j==0){
                    f[i][j]=1;//初始条件
                }
                else{
                    f[i][j]=f[i-1][j]+f[i][j-1];//转移方程
                }
            }
        }
        return f[m-1][n-1];
    }
}

例题三：Jump Game(LeetCode 55)

问题描述：

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
您将获得一个整数数组nums。您最初位于数组的第一个索引处，数组中的每个元素表示该位置处的最大跳转长度。
如果可以到达最后一个索引，则返回true，否则返回false。

在这里插入图片描述

确定状态

  1. 最后一步

    如果能到达n-1,那么我们考虑它的最后一步是从i跳来的（0<=i<n-1）,那就需要满足两个条件

    1. 可以到达i
    2. 最后一步不能超过跳跃的最大距离
  2. 子问题

    我们能不能到达i

状态：设f[j]表示能不能跳到j

转移方程

设f[j]表示能不能跳到j：
f[j]=OR
AND表示前后都要成立
OR表示只有有一种情况满足即可

初始条件和边界情况

初始条件：f[0]=True
没有边界情况

计算顺序

从小到大

小结与代码实现

时间复杂度：O（N^2），空间复杂度（数组大小）：O（N）

注意：对于此题，贪心是更好的解决算法，此处仅仅展示DP可以实现。

class Solution {
    public boolean canJump(int[] nums) {
        int n=nums.length;
        boolean[] f=new boolean[n];
        f[0]=true;//初始条件
        
        for(int j=1;j<n;++j){
            f[j]=false;
            for(int i=0;i<j;++i){
                if(f[i]&&i+nums[i]>=j){//转移方程
                    f[j]=true;
                    break;
                }
            }
        }
        return f[n-1];
    }
}

总结

DP的路刚刚开始，仅仅是以上四步法还不够解决所有问题，革命尚未成功，同志仍需努力！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构与算法

动态规划

算法

动态规划（Dynamic Programming）入门 的相关文章

  • Couldn‘t build proto file into descriptor pool

    这是protobuf二进制的问题 解决该问题的唯一方法是安装纯python的实现 具体如下 pip uninstall protobuf pip install no binary protobuf protobuf

  • url-pattern配置为"/"和"/*"的区别

    url pattern配置为 和 的区别 最近在学习springMVC框架 对于其前端控制器的过滤配置url pattern很困惑 遂百度查各种资料 翻阅各种博客 发现每个人的说法都不一样 很多人的理解都是错的 于是找大牛解惑 大牛就是大牛

  • 使 QComboBox 下拉一个树形结构列表

    背景 在项目开发过程中需要使 QComboBox 下拉一个树形列表 直接通过 setModel 和 setView 设置 combox 控件可以实现 但是在单击节点箭头按钮时也会隐藏下拉框的显示 因此需要重新实现 QComboBox 的方法

随机推荐

  • 怎样用pytorch实现ocr文字识别技术

    要使用PyTorch实现OCR Optical Character Recognition 文字识别技术 可以按照以下步骤 收集和准备数据集 数据集应包括文本图像和相应的标签 标签应该是文本图像中的字符序列 可以使用公共OCR数据集 如MN

  • C++调用tensorflow模型

    开发环境 VS2015 python3 6 tensorflow gpu 1 6 C 测试代码 随便写了一个简单的测试代码 在此之前工程要加上包含路径和库目录 我的python路径为 F Anaconda envs python36 inc

  • Python（二十五）

    一 进程与线程的概念 1 1 进程 考虑一个场景 浏览器 网易云音乐以及notepad 三个软件只能顺序执行是怎样一种场景呢 另外 假如有两个程序A和B 程序A在执行到一半的过程中 需要读取大量的数据输入 I O操作 而此时CPU只能静静地

  • 软件测试的目的、原则及流程

    一 软件测试的目的 1 软件测试是为了发现错误而执行程序的过程 2 测试是为了证明程序有错 而不是证明程序无错 发现错误不是唯一目的 3 一个好的测试用例在于它发现至今未发现的错误 4 一个成功的测试是发现了至今未发现的错误的测试 注意 1

  • JVM--基础--30--hs_err_pid

    JVM 基础 30 hs err pid 1 介绍 当jvm出现致命错误时 会生成一个错误文件 hs err pid log hs err pid log文件 默认会生成到工作目录下 hs err pid log 包括了导致 jvm 崩溃

  • UVA1025 A Spy in the Metro

    UVA1025 A Spy in the Metro 题目链接 刚开始接触DP题 感觉还是有一定的难度 在这里再理一遍思路 DP的核心就是状态和状态转移方程 首先状态的确定就是找到影响当前决策的因素 本题是当前时间和所处车站两个 所以可以用

  • cmu14-445 环境搭建

    0 序 记录自己在克隆bustub时的踩坑经历 1 gtest无法正常运行 虽然bustub的仓库中建立一个私人仓库 然后给出了详细的命令行步骤 但我这个懒人不太想专门去建个仓库 于是就顺手直接把仓库克隆了下来 git clone http

  • 1123. 最深叶节点的最近公共祖先

    文章目录 Tag 题目来源 题目解读 解题思路 方法一 递归 写在最后 Tag 递归 最近公共祖先 二叉树 题目来源 1123 最深叶节点的最近公共祖先 865 具有所有最深节点的最小子树 此二题系重复的题目 题目解读 题目意思很明确 找出

  • 两向量常用的“积”-----------内积，外积，点乘，叉乘，哈达玛积，张量积

    英文叫法总结 目前论文中常出现的几种向量积 1 内积 inner product 点积 点乘 dot product 数量积 scalar product 2 外积 Exterior Product 叉乘 Cross Product 矢量积

  • 微电网优化调度（风、光、储能、柴油机）（Python代码实现）

    欢迎来到本博客 博主优势 博客内容尽量做到思维缜密 逻辑清晰 为了方便读者 座右铭 行百里者 半于九十 目录 1 概述 2 运行结果 3 参考文献 4 Python代码实现 详细文章 数据 文献来源 Python代码复现之 1 概述 电力对

  • wps里的茶色字体怎么设置_如何添加WPS字体 - 卡饭网

    金山WPS字体添加纹理的方法 金山WPS字体添加纹理的方法 在今天的金山WPS文字处理教程中 我们将给大家分享的是给字体添加纹理的方法 这也是WPS特有的功能之一 给字体添加纹理之后 不仅字体变得更美观 醒目了 而且也字体效果与众不同 也更

  • 3ds max 2014 启动出现 error while registering plugins 怎么修复

    这个问题一般出现在重新安装的 3dsmax2013 和 3dsmax2014 上 这是由于卸载残留的文件造成了插件注册冲突导致的 所以我们需要做的就是删除这些残留文件 删除 C 盘用户目录下的这两个文件夹 C Users AppData L

  • 50多个国外的免费Icon图标免费下载网站

    原文出自 帕兰映像 50多个国外的免费Icon图标免费下载网站Icon图标通常应用于对系统的美化和应用程序的UI设计中 但是随着Web2 0的大潮兴起 大而醒目的设计元素也日趋流行 你完全可以把图标应用到网站设计中 比如菜单栏图标 分类图标

  • Linux安装pip没有权限,linux – 从没有root的python3远程安装pip

    我正在尝试通过ssh为远程主机之一安装python3 我没有root访问权限 安装完成了 wget https www python org ftp python 3 7 0 Python 3 7 0 tgz tar xvzf Python

  • C语言——文件的打开和关闭(fopen,fclose函数)

    文章目录 一 为什么使用文件 二 什么是文件 2 1 程序文件 2 2 数据文件 2 3 文件名 三 文件的打开和关闭 3 1文件指针 3 2 文件的打开和关闭 一 为什么使用文件 一般我们写程序时 数据都是存放在内存中 当程序退出后这些数

  • android培训课程！一篇文章教你搞定计算机网络面试，含BATJM大厂

    接触这一行也有很久了 从开始的实习到带团队 中间接触过很多人 前不久身边刚好有人去面试了阿里 抖音等这些公司还成功的面试上了 现在来分享一下面试前需要准备的知识点 很多人去面试之前 不知道会问到那些知识 也不知道要做什么准备 今天我们就来整

  • 利达主机联网接线端子_利达：消防设备电源监控系统接线示意图

    北京利达华信电子有限公司为适应工程设计需要而开发的消防设备电源监控系统符合GB 28184 2011 消防设备电源监控系统 及GB 25506 201 0 消防控制室通用技术要求 等标准 适用于智能楼宇 高层公寓 宾馆 饭店 商厦 工矿企业

  • 关于谷歌浏览器css样式不显示的解决方法

    最近使用IntelliJ IDEA重新回顾html知识 原本使用360浏览器 360浏览器没有这个问题 现在改成使用谷歌浏览器 修改css后运行到谷歌浏览器上 发现并没有显示修改后的效果 本来以为是浏览器有不兼容的问题 后来发现原来谷歌浏览

  • xposed框架安全模式_太极免Root使用Xposed，实现虚拟定位，消息放撤回等神级功能...

    正文 小手壹挥隆重为大家介绍 一款可以免root使用Xposed模块的太极app 下载太极app即可帮助用户实现免root情况下运行Xposed模块 更好的使用辅助插件 太极app是干嘛的 有什么作用 这是一款可以帮助自己手机中应用渡劫的软

  • 动态规划（Dynamic Programming）入门

    前言 算法实验课的题目是一道关于动态规划 Dynamic Programming 的题目 正好借这个机会 学习一下动态规划 Dynamic Programming 动态规划简单介绍 动态规划 Dynamic Programming 简称DP

热门标签