记忆化搜索(搜索+dp思想)

记忆化搜索(搜索+dp思想)一:简介(1)记忆化搜索即搜索+动态规划数组记录上一层计算结果,避免过多的重复计算算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存;一般说来,动态规划总要遍历所有的状态,而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝,可能剪去大量不必要的状态,因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序,但是每求解

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一:简介

(1)记忆化搜索 即 搜索+动态规划数组记录上一层计算结果,避免过多的重复计算

算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存;一般说来,动态规划总要遍历所有的状态,而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝,可能剪去大量不必要的状态,因此在空间开销上往往比动态规划要低很多
记忆化算法在求解的时候还是按着自顶向下的顺序,但是每求解一个状态,就将它的解保存下来,以后再次遇到这个状态的时候,就不必重新求解了
这种方法综合了搜索和动态规划两方面的优点,因而还是很有实用价值的。可以归纳为:记忆化搜索=搜索的形式+动态规划的思想

(2)简单例子

题目描述:已知n个slots,1<n<17,每个slot有一个height,height的值有四种,分别为{1,2,3,4}.给你n个slot的,必须满足以下两个条件,求有多少种情况.  一:必须有两个相邻的slot的差为3,即一个为4,一个为1.    二:必须有三种不同的height值.
Sample Input
2
3
-1
Sample Output
2: 0
3: 8
这道题有组合公式,但想推出来不容易,其实用搜索就能很好地解决。
如果用暴搜的话,当n>10就会超时。这时,很容易想到动态规划,但DP不仅需要推出状态转移方程式,还要进行拓扑排序,对于这题,很难用传统的DP解决。虽然不能使用传统意义上的动态规划解决本题,但动态规划的思想仍然能起到作用。搜索相对于动态规划最大的劣势无非就是重复计算子结构,所以我们在搜索的过程中,对于每一个子结构只计算一次,之后保存到数组里,以后要用到的时候直接调用就可以了,这就是我要介绍的记忆化搜索。
记忆化搜索的实质是动态规划,效率也和动态规划接近,形式是搜索,简单直观,代码也容易编写,不需要进行什么拓扑排序了。
对于状态的存储,可用数组num[a] [b][c][d],其中a为还剩几个,b为找到了哪几个,c为找到的最后一个数,d表示是否已经出现1,4相连的两数

二:案例详解

(1)题目描述:给从左至右排好队的小朋友们分糖果,
要求:1.每个小朋友都有一个得分,任意两个相邻的小朋友,得分较高的所得的糖果必须大于得分较低的,相等则不作要求。
       2.每个小朋友至少获得一个糖果。

求:至少需要的糖果数。
输入:
输入包含多组测试数据,每组测试数据由一个整数n(1<=n<=100000)开头,接下去一行包含n个整数,代表每个小朋友的分数Si(1<=Si<=10000)。
输出:
对于每组测试数据,输出一个整数,代表至少需要的糖果数。

(2)解题报告

所有人的最小能分配到的糖果值就可以通过他的左右两个人计算出来。可以采用记忆化搜索算法。复杂度是O(n);

input:
3
1 10 1
3
6 2 3
2
1 1
output:
4
5
2

(3)代码实现

#include<cstdio>
#include<cstring>
#define MAX 100001
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;

int cal(int r,int n,int dp[],int Arr[])
{
    if(dp[r]>0)
        return dp[r];//已经计算过
    dp[r]=1;
    if(r+1<=n&&Arr[r]>Arr[r+1])//右边有人比他小,要受右边限制
        dp[r]=max(dp[r],cal(r+1,n,dp,Arr)+1);
    if(r-1>=1&&Arr[r]>Arr[r-1])//左边有人比他小,要受左边限制
        dp[r]=max(dp[r],cal(r-1,n,dp,Arr)+1);
    return dp[r];
}

int main(int argc,char *argv[])
{
    int n;
    int Arr[MAX];
    int dp[MAX];
    while(scanf("%d",&n)!=EOF)
    {
        int i;
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            scanf("%d",&Arr[i]);
        long long sum=0;
        for(i=1;i<=n;i++)
            sum+=cal(i,n,dp,Arr);
        printf("%lld\n",sum);
    }

    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164445.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 请画出下面流程图对应的N-S图以及PAD图_软件设计流程图示例

    请画出下面流程图对应的N-S图以及PAD图_软件设计流程图示例在软件程序设计中,我们通常会用到以下几种图,来帮助我们,分析问题,整理逻辑。我将介绍这四种图的特性,以及区分它们的方法。1.N-S图:也叫盒图,由美国学者I.Nassi和B.Shneiderman提出,所以又称N-S图,可以清晰的表示程序的结构以及流程,其主要特征为“矩形框”。2.PAD图:全称为ProblemAnalysisDiagram,即问题分析图表,利用二维树形结构表示…

  • MINI PCI-E接口_pcie接口原理图

    MINI PCI-E接口_pcie接口原理图1、PCIe3.0X4下图只用了2Lanes,pcie接口分x1、x4、x8、x16接口,向下兼容。含一对差分CLK时钟信号上图:pciex4引脚定义2、minipcie和msata接口一样minipcie和msata接口定义是一样的,可以相互交换使用。都是只有1对Tx和1对Rx,没有差分CLK时钟信号。下图是msata接口,常用于系统盘。上图:msata盘上图:minipcie引脚定义上图:msata引脚定义…

  • macports安装卡住_MacPorts下载

    macports安装卡住_MacPorts下载MacPorts类似与apt-get以及yum等软件包管理工具,可以方便的进行安装与卸载软件的功能,同时可以自动安装软件包的依赖,非常方便,同类的还有brew等工具。1.下载及安装下载MacPorts安装包或源码,我比较喜欢源码安装,使用apk安装较慢,而且对进度的把握也不够明显,总感觉程序死掉了。下载以及安装都可以参照 http://www.macports.org/install

  • 存储过程使用数组参数

    存储过程使用数组参数

  • spss k均值聚类_K均值法与系统聚类法的异同

    spss k均值聚类_K均值法与系统聚类法的异同总目录:SPSS学习整理SPSS实现快速聚类(K-Means/K-均值聚类)目的适用情景数据处理SPSS操作SPSS输出结果分析知识点目的利用K均值聚类对数据快速分类适用情景数据处理SPSS操作分析——分类——K-均值聚类最大迭代次数根据数据量,分类数量,电脑情况自己调整,能选多点就把上限调高点。SPSS输出结果分析在数据集最右两列保存了该个案的分类结果与到聚类中心的距离。由于没有自定义初始中心,系统设定了三个。迭代9次后中心值不变。最终个三个聚类中心以及他们

    2022年10月29日
  • 学习web前端,初学者应该用什么编程软件

    学习web前端,初学者应该用什么编程软件Web前端开发最常见的编程软件有以下几种: DreamWeaver是一款老牌前端开发工具,功能强大且组件丰富,作为前端开发的一款利器被广泛使用。DreamWeaver是一款可视化的前端开发工具,一边写代码一边就能看到效果,所以使用起来还是比较方便的。但是DreamWeaver的缺点就是比较耗费系统资源,这也许是IDE类产品的通病。 Hbuilder是最近几年被广泛使用的一款前端开发…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号