Sicily 算法模拟题 1001_中山大学sicily编程平台上机考试-程序员宅基地

技术标签: 算法  动态规划  

1001 函数求值

定义超级和函数F如下:

F(0, n) = n,对于所有的正整数n..
F(k, n) = F(k – 1, 1) + F(k – 1, 2) + … + F(k – 1, n),对于所有的正整数k和n.
 
请实现下面Solution类中计算F(k, n)的函数(1 <= k, n <= 14).
 
class Solution {
public:
       int F(int k, int n) {
             
       }
};
 
例1:F(1, 3) = 6
 
例2:F(2, 3) = 10
 
例3:F(10, 10) = 167960
 
注意:你只需要提交Solution类的代码,你在本地可以编写main函数测试程序,但不需要提交main函数的代码. 注意不要修改类和函数的名称.

分析

动态规划,最简单直接的办法,代码写起来也比较简洁

       F(k,n) = F(k, n - 1) + F(k - 1, n)

class Solution {
public:
    int F(int k, int n) {
        vector<vector<int> > f;
        f.resize(k + 1, vector<int>(n + 1, 0));
    
        for(int i = 0; i <= k; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == 0)
                    f[i][j] = j;
                else f[i][j] = f[i][j - 1] + f[i - 1][j];
            }   
        }
        return f[k][n];
    }
};

还有一种比较笨的办法,就是都算出来

class Solution {
public:
      int F(int k, int n) {
    vector<vector <int> > res(k+1 ,vector<int>(n,0));

    for (int j = 0; j < n; j++) {
        res[0][j] = j + 1;
    }

    for(int i = 1; i <= k; i++) {
        for (int j = 0; j < n; j++) {
            for(int m = 0; m <= j; m++) {
                res[i][j] += res[i - 1][m];
            }
    }

    }
    return res[k][n-1];
}
};                                 



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xu_xyy/article/details/73692544

智能推荐

pytest导入自定义模块报错:ModuleNotFoundError: No module named ‘xxx‘_modulenotfounderror: no module named 'lib-程序员宅基地

文章浏览阅读6k次,点赞4次,收藏10次。代码:import pytestfrom selenium import webdriverfrom lib.webui import loginAndCheck报错:ModuleNotFoundError: No module named 'lib'解决办法:让系统先从当前路径检索。即解决import os, syssys.path.append(os.getcwd())import pytestfrom selenium import webdriverfrom lib.w_modulenotfounderror: no module named 'lib

【项目实战】【多处注释说明!】scrapy爬虫,爬取招聘网站招聘岗位信息_scrapy项目需求分析-程序员宅基地

文章浏览阅读878次。目录一、项目背景二、项目介绍三、需求分析四、新建项目五、项目文件1.配置文件settings2.爬虫文件huawei中间件middlewares其他pycharm TODO功能一、项目背景最近学习了爬虫的一些基础知识,尝试自己去爬取招聘网站的招聘岗位信息,因此就做了这个项目。过程中参考了很多百度回来的知识,怕自己忘了,通过此项目总结记录下学习笔记,也方便后续索引。二、项目介绍此项目是通过scrapy做了两个爬虫,一个爬取社招,一个爬取校招,爬取了huawei招聘网站的校招跟社招的招聘岗位(JD)信息_scrapy项目需求分析

Git学习笔记-程序员宅基地

文章浏览阅读215次。Git学习笔记1.Git是什么Git是一个开源的分布式版本控制系统,可以有效、高速地处理从很小到非常大的项目版本管理。2. 相关概念仓库:存放代码,文档等文件的目录本地仓库远程仓库可以通过 git remote add 建立关联工作区 (Working Directory): 编辑代码修改内容的地方暂存区 (Stage or Index): 数据暂时存放的区域,可以在工作...

python标准库6张思维导图学明白-程序员宅基地

文章浏览阅读2.8w次,点赞346次,收藏2.7k次。先呈上高清下载地址链接:https://pan.baidu.com/s/14x2Cno96vp67qPz0Ee4weA提取码:7j7g1、标准库概览标准库包含:数据库处理,输入输出存储..._python库的思维导图

cygwin 部署php环境,在window中安装cygwin和swoole-程序员宅基地

文章浏览阅读1k次。《在window中安装cygwin和swoole》要点:本文介绍了在window中安装cygwin和swoole,希望对您有用。如果有疑问,可以联系我们。swoole是一个使用C语言编写的PHP扩展,由于swoole框架是只能在LIUNX等系统上运行,在WINDOW上要安装,需要借助cygwin模拟unix环境。那怎么样才能够在windows系统来开发使用swoole扩展呢?当然我们可以使用vm做..._php cygwin swoole

YOLOv5实现佩戴安全帽检测和识别(含佩戴安全帽数据集+训练代码)-程序员宅基地

文章浏览阅读3.2w次,点赞52次,收藏492次。安全帽佩戴检测和识别系统(含数据集+训练代码),安全帽检测,安全帽识别,佩戴安全帽检测和识别_安全帽数据集

随便推点

第二节02 CIM精度以及制作流程_cim数据源精度-程序员宅基地

文章浏览阅读979次,点赞19次,收藏17次。基于采集的连续地形影像为基础,利用自动建模工具,快速生成全国全域三维数据底板,为宏观场景展示提供数据支撑。_cim数据源精度

grafana导入dashboard模板_grafana dashboard模板在哪找-程序员宅基地

文章浏览阅读1k次,点赞10次,收藏7次。grafana导入dashboard模板_grafana dashboard模板在哪找

mybatis整合sqlite_mybatis sqlite-程序员宅基地

文章浏览阅读4.5k次,点赞3次,收藏9次。我这里是配置的双数据源,其中一个是sqlite,一个是Oracle,如果你只使用sqlite一个数据库,那就只需要修改一下数据源配置,直接像使用mysql的那样使用就可以。先导包:<dependency> <groupId>org.xerial</groupId> <artifactId>sqlite-jdbc</artifactId> <version>3.21.0.1</version>&l_mybatis sqlite

第一篇文章-程序员宅基地

文章浏览阅读120次。前言第一次写博客,就总结一下今天学的课程。一、HTML5做了个微博评论留言案例主要功能由js,MySQL来实现,具体细节没听。*$(function() { // 1.监听输入框的实时输入事件 $('.comment').on('propertychange input', function() { // 判断输入框是否有输入内容,如果输入了内容那么将发布按钮解禁,如果没有输入内容那么将发布按钮禁止 if ($(this).val().length > 0) { $(.

Failed to resolve: com.serenegiant:common:4.1.1_could not find com.serenegiant:common:4.1.1-程序员宅基地

文章浏览阅读3.2k次。在使用AndroidUSBCamera项目时出现此问题,查找多处资料基本都无效,此文章记录下亲测有效的方案。问题描述:在https://github.com/jiangdongguo/AndroidUSBCamera下载下来之后导入Android Studio后出现Failed to resolve: com.serenegiant:common:4.1.1解决方法:1、从https://download.csdn.net/download/xw245184020/12414825..._could not find com.serenegiant:common:4.1.1

charles抓取https数据包,举例详细说明(1),腾讯面试java_charles修改数据-程序员宅基地

文章浏览阅读333次,点赞3次,收藏5次。学习技术是一条慢长而艰苦的道路,不能靠一时激情,也不是熬几天几夜就能学好的,必须养成平时努力学习的习惯。所以:贵在坚持!最后再分享的一些BATJ等大厂20、21年的面试题,把这些技术点整理成了视频和PDF(实际上比预期多花了不少精力),包含知识脉络 + 诸多细节,由于篇幅有限,上面只是以图片的形式给大家展示一部分。Mybatis面试专题MySQL面试专题并发编程面试专题555)]MySQL面试专题[外链图片转存中…(img-CyvRe7uF-1711543166556)]并发编程面试专题。_charles修改数据