首页 > 其他分享 >动态规划

动态规划

时间:2024-08-22 14:48:52浏览次数:10  
标签:数列 格子 int 规划 最高分 num 动态 maxScore

问题实例:跳格子 小明和朋友玩跳格子游戏,有n个连续格子,每个格子有不同的分数,小朋友可以选择以任意格子起跳,但是不能跳连续的格子,也不能回头跳;
给定一个代表每个格子得分的非负整数数组,计算能够得到的最高分数。
输入描述:
给定一个数列,如:1231
1 < nums.length < 100
0 <= nums[i] <= 1000
输出描述:
输出能够得到的最高分,如:
示例1:
输入:
2 7 9 3 1
输出:
12 */

#define max(a, b) ((a) > (b) ? (a) : (b))

思考方向:
数列:1 2 3 ... n-2 n-1 n
首先,函数中定义一个整型数组,用于存储跳n个格子的最高分int maxScore[128],maxScore[0]直接定义为零,因为跳零个格子分数就是零。
跳n个格子,因为不能跳连续的格子,maxScore[n]最高分有两种情况
情况1,maxScore[n-2]+num[n-1]
情况2,maxScore[n-1]
那么最高分取max宏定义高的就是解这个问题的算法逻辑,maxScore[n] = max(maxScore[n-2]+num[n-1], maxScore[n-1])
然后,将数列的首地址和数列长度传入函数进行计算

int getMax(int num[], int n)
{
    int maxScore[128] = {0};
    maxScore[1] = num[0];

    for (int i = 2; i <= n; i++)
    {
        maxScore[i] = max(maxScore[i-2]+num[i-1], maxScore[i-1]);
    }
    return maxScore[n];
}

 

标签:数列,格子,int,规划,最高分,num,动态,maxScore
From: https://www.cnblogs.com/kbqlm/p/18373869

相关文章

  • element plus el-table 合并行或列(根据列表数据动态合并第一列重复的单元格)
    http://element-plus.org/zh-CN/component/table.html#%E5%90%88%E5%B9%B6%E8%A1%8C%E6%88%96%E5%88%97 <scriptsetup>import{onMounted,ref}from'vue'import'./index.css'constobjectSpanMethod=({row,column,rowInde......
  • WPF中如何使用后台代码动态创建数据模板(DataTemplate)
    数据模板回顾 在WPF中数据模板可以控制数据的呈现方式。对于一些简单的数据,例如一个string,一个int,在显示时,无须额外控制。但是对于复杂数据类型,就需要使用数据模板来控制数据的呈现方式。 一个很简单的例子假设我们定义了一个学生类1publicclassStudent2......
  • 题解:P9788 [ROIR 2020 Day2] 区域规划
    题目传送门思路首先我们看下数据范围,$n<=3000$,范围很小,所以暴力枚举。于是第一份代码出来了。#include<bits/stdc++.h>usingnamespacestd;ints,a,b,c,d,n,m;intmain(){ ios::sync_with_stdio(false); cin.tie(),cout.tie(); cin>>n>>m; for(a=1;a<=n;a++) {......
  • 动态树笔记
    不知道“树链剖分”、“全局平衡二叉树”等应不应该归类到“动态树”里面...解决动态树问题的本质是将原树映射到一个高度为\(O(\logn)\)的树上。树链剖分主要是重链剖分,具体略.支持:链修改链查询子树修改子树查询这里的修改、查询需要满足可以用数据结构维护.一般......
  • 算法笔记|Day32动态规划V
    算法笔记|Day32动态规划V※※※※※完全背包问题理论基本题目描述题目分析采用一维数组(滚动数组)☆☆☆☆☆leetcode518.零钱兑换II题目分析代码☆☆☆☆☆leetcode377.组合总和Ⅳ题目分析代码☆☆☆☆☆KamaCoder57.爬楼梯(待补充)题目分析代码※※※※※完全......
  • C语言实现通讯录-动态版本与文件版本
    C语言实现通讯录-动态版本与文件版本1.前言2.动态版本2.1联系人信息之前的:改版:2.2初始化之前的:改版:2.3自动扩容3.文件版本3.1自动保存函数实现:效果:3.2打开时加载信息函数实现:效果:1.前言在先前的探索中,我构建了一个C语言实现简单的通讯录,它能够存储一定数量的......
  • 动态规划(一)
    动态规划(一)多阶段决策问题动态规划是运筹学的一个分支,是求解多阶段决策过程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用,并且获得了显著的效果。学习动态规划,我们首先要了解多阶段决策问题。最短路径问题:背包问......
  • Eureka中的多实例配置:如何处理微服务实例动态扩展与缩减
    Eureka中的多实例配置:如何处理微服务实例动态扩展与缩减1.引言在微服务架构中,服务的动态扩展与缩减是确保系统弹性和高可用性的关键因素。Eureka,作为一个服务注册和发现的组件,扮演着至关重要的角色。它由Netflix开源,广泛应用于SpringCloud生态系统,用于管理微服务实例的......
  • AcWing 1078. 旅游规划 (DFS找树的直径+直径中点性质求解,无DP)
    原题链接题目描述算法引用自树的直径-OI-Wiki:若树上所有边边权均为正,则树的所有直径中点重合证明:使用反证法。设两条中点不重合的直径分别为\(\delta(s,t)与\delta(s',t')\),中点分别为\(x\)与\(x'\)。显然,\(\delta(s,x)=\delta(x,t)=\delta(s',x')=\delta(......
  • 面试+算法之动态规划(Java):斐波那契、背包问题、走棋盘、分苹果、连续子数组最大和、
    概述Dynamicprogramming,简称DP,动态规划,基础算法之一,维基百科的解释:是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时......