【C++刷题】优选算法——动态规划第一辑

1.状态表示
	是什么？简答理解是dp表里的值所表示的含义
	怎么来的？
		题目要求
		经验+题目要求
		分析问题的过程中，发现重复子问题
2.状态转移方程
	dp[i]=......

细节问题：
	3.初始化
		控制填表的时候不越界
	4.填表顺序
		控制在填写当前状态的时候，所需要的状态已经填写好了
	5.返回值
		题目要求+状态表示

空间优化
	滚动数组
  1. 第 N 个泰波那契数
int tribonacci(int n)
{
    // 处理一些边界情况
    if(n < 3)
    {
        if(n == 0) return 0;
        else return 1;
    }

    // 1.创建dp表
    vector<int> dp(n + 1);
    // 2.初始化
    dp[0] = 0, dp[1] = 1, dp[2] = 1;
    for(int i = 3; i <= n; ++i)
    {
        // 3.填表
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    // 4.返回值
    return dp[n];
}
// 空间优化版本
int tribonacci(int n)
{
    int arr[3] = { 0,1,1 };
    if(n < 3) return arr[n];

    int ret = 0;
    for(int i = 3; i <= n; ++i)
    {
        ret = arr[0] + arr[1] + arr[2];
        arr[0] = arr[1], arr[1] = arr[2], arr[2] = ret;
    }
    return ret;
}
  1. 三步问题
状态表示:
	经验+题目要求：以i位置为结尾来入手
	dp[i]: 表示到达i位置，一共有多少种方法
状态转移方程:
	基于i位置状态，跨一步到i位置，来划分问题

int waysToStep(int n)
{
    if(1 == n) return 1;
    else if(2 == n) return 2;
    else if(3 == n) return 4;

    // 1.dp数组
    vector<int> dp(n + 1);
    // 2.初始化
    dp[1] = 1, dp[2] = 2, dp[3] = 4;
    for(int i = 4; i <= n; ++i)
    {
        // 3.状态方程
        dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;
    }
    // 4.返回值
    return dp[n];
}
  1. 使用最小花费爬楼梯
状态表示:
	经验+题目要求：以i位置为结尾来入手
	dp[i]: 表示i位置到下一步的最小花费
状态转移方程:
	dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

int minCostClimbingStairs(vector<int>& cost)
{
    // 1.dp数组
    vector<int> dp(cost.size());
    // 2.初始化
    dp[0] = cost[0]; dp[1] = cost[1];
    for (int i = 2; i < dp.size(); ++i)
    {
        // 3.状态转移方程
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    // 4.返回值
    return min(dp[dp.size() - 1], dp[dp.size() - 2]);
}
  1. 解码方法
状态表示:
	经验+题目要求：以i位置为结尾来入手
	dp[i]: 表示以i位置为结尾时，解码方法的总数
状态转移方程:

在这里插入图片描述

int numDecodings(string s)
{
    // 0.边界情况
    if(s.size() < 2)
    {
        if(s[0] == '0') return 0;
        else return 1;
    }
    // 1.dp数组
    vector<int> dp(s.size(), 0);
    // 2.初始化
    if (s[0] == '0') dp[0] = 0;
    else dp[0] = 1;
    if (s[0] != '0' && s[1] != '0') dp[1] += 1;
    if (10 <= stoi(s.substr(0, 2)) && stoi(s.substr(0, 2)) <= 26) dp[1] += 1;

    for(int i = 2; i < dp.size(); ++i)
    {
        // 3.状态转移方程
        int num1 =0, num2 = 0;
        if(s[i] != '0') num1 = dp[i - 1];
        if(10 <= stoi(s.substr(i - 1, 2)) && stoi(s.substr(i - 1, 2)) <= 26) num2 = dp[i - 2];
        dp[i] = num1 + num2;
    }
    // 4.返回值
    return dp.back();
}
  1. 不同路径
状态表示:
	经验+题目要求：以[i,j]位置为结尾来入手
	dp[i][j]: 表示以[i,j]位置为finish时，从start出发的不同路径数
状态转移方程:
	dp[i][j] = dp[i-1][j] + dp[i][j-1]

int uniquePaths(int m, int n)
{
    // 1.dp数组
    vector<vector<int>> dp(m, vector<int>(n));
    // 2.初始化
    for (int i = 0; i < m; ++i)
    {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; ++i)
    {
        dp[0][i] = 1;
    }
    // 3.状态转移方程
    for (int row = 1; row < m; ++row)
    {
        for (int col = 1; col < n; ++col)
        {
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
        }
    }
    // 4.返回值
    return dp.back().back();
}
  1. 不同路径 II
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
    // 1.dp数组
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    // 2.初始化
    for(int i = 0; i < m; ++i)
    {
        if(obstacleGrid[i][0] == 1)
            break;
        dp[i][0] = 1;
    }
    for(int i = 0; i < n; ++i)
    {
        if(obstacleGrid[0][i] == 1)
            break;
        dp[0][i] = 1;
    }
    // 3.状态转移方程
    for(int row = 1; row < m; ++row)
    {
        for(int col = 1; col < n; ++col)
        {
            if(obstacleGrid[row][col] == 1)
                continue;
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
        }
    }
    // 4.返回值
    return dp.back().back();
}
  1. 珠宝的最高价值
状态表示:
	经验+题目要求：以[i,j]位置为结尾来入手
	dp[i][j]: 表示到达[i,j]位置时所能得到的的最大价值
状态转移方程:
	dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i][j]

int jewelleryValue(vector<vector<int>>& frame)
{
    // 1.dp数组
    int row = frame.size();
    int col = frame[0].size();
    vector<vector<int>> dp(row, vector<int>(col));

    // 2.初始化
    dp[0][0] = frame[0][0];
    for(int i = 1; i < col; ++i)
    {
        dp[0][i] = dp[0][i - 1] + frame[0][i];
    }
    for(int i = 1; i < row; ++i)
    {
        dp[i][0] = dp[i - 1][0] + frame[i][0];
    }

    // 3.状态转移方程
    for(int i = 1; i < row; ++i)
    {
        for(int j = 1; j < col; ++j)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];
        }
    }

    // 4.返回值
    return dp.back().back();
}
  1. 下降路径最小和
状态表示:
	经验+题目要求：以[i,j]位置为结尾来入手
	dp[i][j]: 表示到达[i,j]位置时所得到的最小下降路径和
状态转移方程:
	dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + frame[i][j]

    int minFallingPathSum(vector<vector<int>>& matrix)
    {
        // 1.dp数组
        int n = matrix.size();
        vector<vector<int>> dp(n, vector<int>(n));

        // 2.初始化
        for(int i = 0; i < n; ++i)
        {
            dp[0][i] = matrix[0][i];
        }

        // 3.状态转移方程
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(j == 0)
                {
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
                }
                else if(j == n - 1)
                {
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j];
                }
                else
                {
                    dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i][j];
                }
            }
        }

        // 4.返回值
        int min_sum = dp[n - 1][0];
        for(int i = 1; i < n; ++i)
        {
            if(dp[n - 1][i] < min_sum) min_sum = dp[n - 1][i];
        }
        return min_sum;
    }
  1. 最小路径和
状态表示:
	经验+题目要求：以[i,j]位置为结尾来入手
	dp[i][j]: 表示到达[i,j]位置时所得到的最小路径和
状态转移方程:
	dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

int minPathSum(vector<vector<int>>& grid)
{
    // 1.dp数组
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));

    // 2.初始化
    dp[0][0] = grid[0][0];
    for(int i = 1; i < m; ++i)
    {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for(int i = 1; i < n; ++i)
    {
        dp[0][i] = dp[0][i - 1] + grid[0][i];
    }

    // 3.状态转移方程
    for(int i = 1; i < m; ++i)
    {
        for(int j = 1; j < n; ++j)
        {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    // 4.返回值
    return dp.back().back();
}
  1. 地下城游戏
状态表示:
	经验+题目要求：以[i,j]位置为起点来入手
	dp[i][j]: 表示从[i,j]位置出发，到达终点，所需的最低初始健康点数
状态转移方程:
	dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
	dp[i][j] = max(1, dp[i][j]); // 细节处理，健康点数至少为1才能存活

int calculateMinimumHP(vector<vector<int>>& dungeon)
{
    // 1.dp数组
    int m = dungeon.size();
    int n = dungeon[0].size();
    vector<vector<int>> dp(m, vector<int>(n));

    // 2.初始化
    if(dungeon[m - 1][n - 1] < 0) dp[m - 1][n - 1] = 1 - dungeon[m - 1][n - 1];
    else dp[m - 1][n - 1] = 1;
    for(int i = n - 2; i >= 0; --i)
    {
        dp[m - 1][i] = dp[m - 1][i + 1] - dungeon[m - 1][i];
        dp[m - 1][i] = max(1, dp[m - 1][i]);
    }
    for(int i = m - 2; i >= 0; --i)
    {
        dp[i][n - 1] = dp[i + 1][n - 1] - dungeon[i][n - 1];
        dp[i][n - 1] = max(1, dp[i][n - 1]);
    }

    // 3.状态转移方程
    for(int i = m - 2; i >= 0; --i)
    {
        for(int j = n - 2; j >= 0; --j)
        {
            dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            dp[i][j] = max(1, dp[i][j]);
        }
    }

    // 4.返回值
    return dp[0][0];
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/464427.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【S5PV210_视频编解码项目】裸机开发：实现按键的外部中断处理

【S5PV210_视频编解码项目】裸机开发：实现按键的外部中断处理

加粗样式本文所作内容&#xff1a; 基于S5PV210芯片实现按键的外部中断处理程序&#xff0c;搭建中断处理流程框架 S5PV210对于中断处理的操作流程 1 外部中断得到触发&#xff1a; 1&#xff09;外部中断在初始化阶段得到使能 2&#xff09;外界达到了外部中断的触发条件 …
阅读更多...
手机网络连接性能API接口：查询手机网络连接性能状态

手机网络连接性能API接口：查询手机网络连接性能状态

手机在网状态查询服务是一项非常方便的服务&#xff0c;可以帮助我们随时了解一个手机号码的在网状态。不论是查询自己的手机号码&#xff0c;还是查询他人的手机号码&#xff0c;这个服务都可以帮助我们获取准确的信息。今天&#xff0c;我想和大家介绍一个非常好用的手机在网…
阅读更多...
运用html相关知识编写导航栏和二级菜单

运用html相关知识编写导航栏和二级菜单

相关代码&#xff1a; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title><s…
阅读更多...
30.HarmonyOS App(JAVA)鸿蒙系统app多线程任务分发器

30.HarmonyOS App(JAVA)鸿蒙系统app多线程任务分发器

HarmonyOS App(JAVA)多线程任务分发器 打印时间&#xff0c;记录到编辑框textfield信息显示 同步分发&#xff0c;异步分发&#xff0c;异步延迟分发&#xff0c;分组任务分发&#xff0c;屏蔽任务分发&#xff0c;多次任务分发 参考代码注释 场景介绍 如果应用的业务逻辑比…
阅读更多...
【技术类-04】python实现docx表格文字和段落文字的“手动换行符（软回车）”变成“段落标记（硬回车）”

【技术类-04】python实现docx表格文字和段落文字的“手动换行符（软回车）”变成“段落标记（硬回车）”

作品展示&#xff1a; 背景需求&#xff1a; 把python实现docx表格文字和段落文字的“手动换行符&#xff08;软回车&#xff09;”变成“段落标记&#xff08;硬回车&#xff09;合并在一起统计数量 【技术类-02】python实现docx段落文字的“手动换行符&#xff08;软回车&a…
阅读更多...
Prometheus 轻量化部署和使用

Prometheus 轻量化部署和使用

文章目录 说明Prometheus简介Grafana简介prometheus和Grafana的关系环境准备&#xff08;docker&#xff09;docker安装时间时区问题&#xff08;我的代码中&#xff09;dockers镜像加速和服务器时区设置 数据库准备(mysql、redis)mysql配置redis配置 Prometheus、grafana下载和…
阅读更多...
4-如何进行细分市场分析-03 竞争者分析

4-如何进行细分市场分析-03 竞争者分析

任何一个行业肯定都是有很多竞争者&#xff0c;我们如何判断这些竞争者对我们有什么样的威胁、什么样的机会、什么样的影响&#xff0c;我们需要去分析这些竞争者。 行业竞争格局如何分析&#xff1f; 我们可以从一些基本指标来入手&#xff0c;如市场集中度、行业利润率。 竞…
阅读更多...
Win10系统使用IIS服务搭建WebDAV网站结合内网穿透公网访问本地文件

Win10系统使用IIS服务搭建WebDAV网站结合内网穿透公网访问本地文件

文章目录 推荐1. 安装IIS必要WebDav组件2. 客户端测试3. cpolar内网穿透3.1 打开Web-UI管理界面3.2 创建隧道3.3 查看在线隧道列表3.4 浏览器访问测试 4. 安装Raidrive客户端4.1 连接WebDav服务器4.2 连接成功4.2 连接成功总结&#xff1a; 推荐 前些天发现了一个巨牛的人工智能…
阅读更多...
短剧小程序软件开发首页接口转发到Selectpage

短剧小程序软件开发首页接口转发到Selectpage

工具&#xff1a;用的是uniapp开发 技术栈&#xff1a;vue、nide..js、云开发 用时&#xff1a;20工作天 软件&#xff1a;Hb、微信开发者工具 <?php namespace app\api\controller; use app\common\controller\Api; /** * 首页接口 */ class Index extends Api { …
阅读更多...
算法思想总结：滑动窗口算法

算法思想总结：滑动窗口算法

创作不易&#xff0c;感谢三连 一.长度最小的数组 . - 力扣&#xff08;LeetCode&#xff09;长度最小的数组 class Solution { public:int minSubArrayLen(int target, vector<int>& nums) {int lenINT_MAX,nnums.size(),sum0;//len必须要给一个很大的数&#xf…
阅读更多...
【LeetCode每日一题】2684. 矩阵中移动的最大次数

【LeetCode每日一题】2684. 矩阵中移动的最大次数

文章目录 [2684. 矩阵中移动的最大次数](https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/)思虑&#xff1a;代码&#xff1a; 2684. 矩阵中移动的最大次数 思虑&#xff1a; 1.将第一列的所有行坐标&#xff0c;用IntStream 来生成一个范围 [0, m) 内的整数…
阅读更多...
reloading，一个很实用的Python库！

reloading，一个很实用的Python库！

Python是一门非常流行的编程语言&#xff0c;它的广泛应用和丰富的第三方库使得开发者们能够轻松完成各种任务。reloading是Python中一个强大的库&#xff0c;它能够在程序运行时重新加载修改过的模块&#xff0c;为开发者提供了便利和灵活性。本文将全面介绍reloading库&#…
阅读更多...
警惕MKP勒索病毒，您需要知道的预防和恢复方法。

警惕MKP勒索病毒，您需要知道的预防和恢复方法。

引言&#xff1a; 在网络世界中&#xff0c;.mkp勒索病毒是一股威胁不可小觑的黑暗势力。它以其毒辣的加密手段威胁着我们的数据安全。本文将深入介绍.mkp勒索病毒&#xff0c;揭示如何恢复被其加密的数据文件&#xff0c;并分享一些预防措施&#xff0c;助您在数字世界中安全…
阅读更多...
整数和浮点数在内存中存储及题目

整数和浮点数在内存中存储及题目

一、整数在内存中存储 整数的2进制表⽰⽅法有三种&#xff0c;即原码、反码和补码。三种表⽰⽅法均有符号位和数值位两部分&#xff0c;符号位都是⽤0表⽰“正”&#xff0c;⽤1表⽰“负”&#xff0c;⽽数值位最⾼位的⼀位是被当做符号位&#xff0c;剩余的都是数值位 正整数…
阅读更多...
使用ChatGPT高效完成简历制作[中篇]-有爱AI实战教程(五）

使用ChatGPT高效完成简历制作[中篇]-有爱AI实战教程(五）

演示站点&#xff1a; https://ai.uaai.cn 对话模块 官方论坛&#xff1a; www.jingyuai.com 京娱AI 导读&#xff1a;在使用 ChatGPT 时&#xff0c;当你给的指令越精确&#xff0c;它的回答会越到位&#xff0c;举例来说&#xff0c;假如你要请它帮忙写文案&#xff0c;如果没…
阅读更多...
【JS进阶】第一天

【JS进阶】第一天

参考视频——黑马程序员 JavaScript 进阶 - 第 1 天 学习作用域、变量提升、闭包等语言特征&#xff0c;加深对 JavaScript 的理解&#xff0c;掌握变量赋值、函数声明的简洁语法&#xff0c;降低代码的冗余度。 理解作用域对程序执行的影响能够分析程序执行的作用域范围理解闭…
阅读更多...
后端程序员入门react笔记（八）-redux的使用和项目搭建

后端程序员入门react笔记（八）-redux的使用和项目搭建

一个更好用的文档 添加链接描述 箭头函数的简化 //简化前 function countIncreAction(data) {return {type:"INCREMENT",data} } //简化后 const countIncreAction data>({type:"INCREMENT",data })react UI组件库相关资料 组件库连接和推荐 antd组…
阅读更多...
electron 学习

electron 学习

const { app, BrowserWindow } require(electron); const path require(path); function createWindow () {let mainWin new BrowserWindow({x: 100,y: 100,show:false, // 默认不显示窗体width: 800,height: 800,maxHeight: 1000,maxWidth: 1000,minHeight: 400,minWidth: …
阅读更多...
Linux学习（4）——使用编辑器

Linux学习（4）——使用编辑器

1.gedit编辑器 简单易懂&#xff0c;依赖图形界面。可以使用ctrlc ctrlv等快捷键&#xff0c;ctrls进行保存&#xff0c;与windows系统中相类似。 2.vi/vim编辑器 vi/vim可以直接通过控制台的终端完成文本的编辑&#xff0c;不依赖图形界面&#xff0c;使用范围更广。它的编辑…
阅读更多...
安装Pytorch——CPU版本

安装Pytorch——CPU版本

安装Pytorch——CPU版本 1. 打开pytorch官网2. 选择pip安装pytorch-cpu3.复制安装命令4. 在cmd命令窗口&#xff0c;进入你的虚拟环境4.1 创建虚拟环境4.2 进行安装 5. 安装成功6. 进行测试——如下面步骤&#xff0c;如图6.1 输入 python6.2 输入 import torch6.2 输入 print …
阅读更多...
最新文章

Copyright @ 2022~2023