c++中如何实现动态规划最小路径和_c++动态规划最小路径和实现方法

裘德小鎮的故事

发布时间：2025-10-01 15:20:02

478人浏览过

来源于php中文网

原创

最小路径和可通过动态规划求解，定义dpi为从起点到(i,j)的最小和，状态转移方程为dpi=gridi+min(dpi-1,dpi)，初始化第一行和第一列后遍历填充，最终结果为dpm-1。

c++中如何实现动态规划最小路径和_c++动态规划最小路径和实现方法

在C++中实现动态规划求解“最小路径和”问题，通常应用于二维网格中从左上角到右下角的路径选择。目标是找出一条路径，使得路径上所有数字的和最小，每次只能向下或向右移动。

问题描述

给定一个 m × n 的非负整数网格 grid，找出从左上角到右下角的路径，使得路径上的数字总和最小。只能向下或向右移动。

动态规划思路

使用动态规划来避免重复计算。定义 dp[i][j] 表示从起点 (0,0) 到位置 (i,j) 的最小路径和。状态转移方程：

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

边界处理：

第一行：只能从左向右走，dp[0][j] = dp[0][j-1] + grid[0][j]
第一列：只能从上向下走，dp[i][0] = dp[i-1][0] + grid[i][0]

C++ 实现代码

可以直接在原数组上修改以节省空间，或者创建一个新的 dp 数组。以下是使用原数组进行空间优化的版本：

代码示例：

奇布塔

基于AI生成技术的一站式有声绘本创作平台

下载

#include 
#include 
#include 
using namespace std;

int minPathSum(vector>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    
    int m = grid.size();
    int n = grid[0].size();

    // 初始化第一列
    for (int i = 1; i < m; ++i) {
        grid[i][0] += grid[i-1][0];
    }

    // 初始化第一行
    for (int j = 1; j < n; ++j) {
        grid[0][j] += grid[0][j-1];
    }

    // 填充其余位置
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
        }
    }

    return grid[m-1][n-1];
}

// 测试示例
int main() {
    vector> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    cout << "最小路径和: " << minPathSum(grid) << endl;
    return 0;
}

复杂度分析

时间复杂度：O(m × n)，需要遍历整个网格一次。
空间复杂度：O(1)，直接在原数组上修改，没有使用额外空间（如果不允许修改原数组，则需 O(m × n)）。

基本上就这些。这种方法简洁高效，适合大多数最小路径和类题目。注意边界判断和初始化顺序即可。

C++ 怎么获取环境变量 C++ getenv函数读取系统变量【环境】

C++ 怎么实现单例 C++ Meyer's Singleton线程安全写法【模式】

C++ 怎么实现多态 C++虚函数与动态绑定机制详解【面试】

C++析构函数什么时候调用 C++对象生命周期管理详解【机制】

C++怎么用OpenGL C++图形学编程环境GLFW配置指南【图形】

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

c++ go ai ios stream

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++怎么在运行时动态加载库（dlopen/LoadLibrary）_c++运行时动态加载库方法下一篇：c++怎么使用Conan包管理器_c++ Conan包管理器使用方法

作者最新文章

Composer怎么发布自己的包提交代码到Packagist流程【分享】

2026-01-26 14:07

Linux如何查看网络流量_Linux流量监控工具nload与iftop【教程】

2026-01-26 14:08

转转app怎么关闭个性化推荐转转app隐私设置在哪里【建议】

2026-01-26 14:08

漫蛙备用网址入口2026 漫蛙网页版在线浏览指南

2026-01-26 14:08

C++ future和promise C++ 异步编程结果传递【并发编程】

2026-01-26 14:14

Yandex官网镜像入口_俄罗斯Yandex搜索引擎网页版在线

2026-01-26 14:15

tplogin.cn管理页面 tplink无线路由器官网

2026-01-26 14:15

Win11怎么查看系统日志 Win11事件查看器使用教程【故障】

2026-01-26 14:16

Mac怎么使用听写功能 Mac语音输入文字设置方法【妙招】

2026-01-26 14:18

AO3有效网址链接_Archive of Our Own官方通道

2026-01-26 14:18

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发 AI 聊天问答

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发 AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI 编程开发 Agent智能体

腾讯元宝

腾讯混元平台推出的AI助手

文档处理 AI 聊天问答

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发 AI 文本写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发 AI 文本写作

智谱清言 - 免费全能的AI助手

AI 编程开发 Agent智能体

相关专题

俄罗斯Yandex引擎入口

2026年俄罗斯Yandex搜索引擎最新入口汇总，涵盖免登录、多语言支持、无广告视频播放及本地化服务等核心功能。阅读专题下面的文章了解更多详细内容。

178

2026.01.28

包子漫画在线官方入口大全

本合集汇总了包子漫画2026最新官方在线观看入口，涵盖备用域名、正版无广告链接及多端适配地址，助你畅享12700+高清漫画资源。阅读专题下面的文章了解更多详细内容。

2026.01.28

ao3中文版官网地址大全

AO3最新中文版官网入口合集，汇总2026年主站及国内优化镜像链接，支持简体中文界面、无广告阅读与多设备同步。阅读专题下面的文章了解更多详细内容。

2026.01.28

php怎么写接口教程

本合集涵盖PHP接口开发基础、RESTful API设计、数据交互与安全处理等实用教程，助你快速掌握PHP接口编写技巧。阅读专题下面的文章了解更多详细内容。

2026.01.28

php中文乱码如何解决

本文整理了php中文乱码如何解决及解决方法,阅读节专题下面的文章了解更多详细内容。

2026.01.28

Java 消息队列与异步架构实战

本专题系统讲解 Java 在消息队列与异步系统架构中的核心应用，涵盖消息队列基本原理、Kafka 与 RabbitMQ 的使用场景对比、生产者与消费者模型、消息可靠性与顺序性保障、重复消费与幂等处理，以及在高并发系统中的异步解耦设计。通过实战案例，帮助学习者掌握使用 Java 构建高吞吐、高可靠异步消息系统的完整思路。

2026.01.28

Python 自然语言处理（NLP）基础与实战

本专题系统讲解 Python 在自然语言处理（NLP）领域的基础方法与实战应用，涵盖文本预处理（分词、去停用词）、词性标注、命名实体识别、关键词提取、情感分析，以及常用 NLP 库（NLTK、spaCy）的核心用法。通过真实文本案例，帮助学习者掌握使用 Python 进行文本分析与语言数据处理的完整流程，适用于内容分析、舆情监测与智能文本应用场景。

2026.01.27