文档章节

路径数目 & 最小路径和 c++

datacube
 datacube
发布于 2017/04/09 11:03
字数 378
阅读 23
收藏 0
#include <iostream>
#include <vector>
#include <limits>
using namespace std;

/*
思路:对于某一点dp[i][j]的路径数目,是该点正上方和正左方路径数目之和
dp[i][j] = dp[i][j-1] + dp[i-1][j]; 但是对于特殊地方需要特殊考虑 
*/

int Unique_path(int m,int n,int first,int second)
{
	vector<vector<int> > dp(m);
	int i,j;
	for(i=0;i<dp.size();i++)
		dp[i].assign(n,0);
	dp[0][0] =1;
	for(i=0;i<dp.size();i++)
	{
		for(j=0;j<dp[0].size();j++)
		{
			if(i!=0 || j!=0)
			{
				if(i == first && j == second)
					dp[i][j] =0;
				else
				{
					if(i == 0)
						dp[i][j] = dp[i][j-1];
					else if(j== 0)
						dp[i][j] = dp[i-1][j];
					else
						dp[i][j] = dp[i][j-1]+dp[i-1][j];
				}
			}
		}
	} 
	return dp[m-1][n-1];
} 

/*
第二个问题,从左上角到右下角,寻找代价最小的路径 
典型的动态规划问题,和上个问题类似
*/

int MinPathSum(vector<vector<int> >& vec)
{
	vector<vector<int> > dp(vec.size());
	int i,j;
	for(i=0;i<vec.size();i++)
		dp[i].assign(vec[i].size(),numeric_limits<int>::max());
	dp[0][0] = vec[0][0];
	for(i=1;i<vec.size();i++)
		dp[i][0] = vec[i][0]+dp[i-1][0];
	for(j=1;j<vec[0].size();j++)
		dp[0][j] = vec[0][j] + dp[0][j-1];
	
	int tmp;
	for(i=1;i<vec.size();i++)
	{
		for(j=1;j<vec[0].size();j++)
		{
			tmp = min(vec[i][j]+dp[i][j-1],vec[i][j]+dp[i-1][j]);
			dp[i][j] = min(dp[i][j],tmp);
		}		
 	}
	return dp[vec.size()-1][vec[0].size()-1];
} 


int main()
{
//	cout << Unique_path(3,7,2,3)<<endl;
	vector<vector<int> > vec(3);
	int i,j;
	int array[]={2,4,3,7};
	int array1[]={5,3,2,1};
	int array2[]={4,8,6,2};
	vec[0].assign(array,array+4);
	vec[1].assign(array1,array1+4);
	vec[2].assign(array2,array2+4);
	cout<<MinPathSum(vec)<<endl;
	return 0;
} 

© 著作权归作者所有

上一篇: git回退
datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问
PAT 1018. Public Bike Management

整体思路很简单,仅仅涉及到一个dfs,得到0到某一点的路径,在从中记录下满足条件的路径。条件:距离最小,车携带数量最小,剩余自行车的数量最少。 C++代码 #include <stdio.h> include <io...

guoliang
2013/09/14
2.4K
4
贪心算法之最短路径问题(Dijkstra算法)

1、问题 一个求单源最短路径的问题。给定有向带权图 G =(V, E ), 其中每条边的权是非负实数。此外,给定 V 中的一个顶点, 称为源点。现在要计算从源到所有其他各顶点的最短路径长 度,这里路径...

u011068702
2018/01/24
0
0
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
1K
0
让控制台应用程序支持MFC类库

1、 问题阐述:在基于控制台的应用程序中并不支持MFC库,如果使基于控制台的应用程序能够使用MFC类库呢? 2、 实现技巧:在控制台应用程序中通过include来引入MFC库,因为控制台应用程序默认...

Amamatthew
2014/06/16
3.3K
0
Android Studio 2.2 更方便地创建JNI项目-CMake

前段时间写了篇Android Studio 第一个NDK例子,它是在使用版本的实现方案,最近发现稳定版本已经出来了,所以更新了版本,发现使用该版本创建Jni项目更加方便了。 使用Android Studio 2.2创建...

shzwork
03/30
3
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql-connector-java升级到8.0后保存时间到数据库出现了时差

在一个新项目中用到了新版的mysql jdbc 驱动 <dependency>     <groupId>mysql</groupId>     <artifactId>mysql-connector-java</artifactId>     <version>8.0.18</version> ......

ValSong
40分钟前
5
0
Spring Boot 如何部署到 Linux 中的服务

打包完成后的 Spring Boot 程序如何部署到 Linux 上的服务? 你可以参考官方的有关部署 Spring Boot 为 Linux 服务的文档。 文档链接如下: https://docs.ossez.com/spring-boot-docs/docs/r...

honeymoose
42分钟前
5
0
Spring Boot 2 实战:使用 Spring Boot Admin 监控你的应用

1. 前言 生产上对 Web 应用 的监控是十分必要的。我们可以近乎实时来对应用的健康、性能等其他指标进行监控来及时应对一些突发情况。避免一些故障的发生。对于 Spring Boot 应用来说我们可以...

码农小胖哥
今天
6
0
ZetCode 教程翻译计划正式启动 | ApacheCN

原文:ZetCode 协议:CC BY-NC-SA 4.0 欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 学习资源 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 ...

ApacheCN_飞龙
今天
4
0
CSS定位

CSS定位 relative相对定位 absolute绝对定位 fixed和sticky及zIndex relative相对定位 position特性:css position属性用于指定一个元素在文档中的定位方式。top、right、bottom、left属性则...

studywin
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部