给出一个m*n的数字矩阵，问从第一列任意行出发（只能直走，右下，左下），到最后一列所经数字的最小路径是什么，如果有多解，输出字典序最小解.
这个矩阵第一行的上一行是最后一行，最后一行的下一行是第一行
我们定义状态d(j,i)表示当前在第j列，第i行，当前数字和是多少。初始边界就是第一列的数字等于它自身.
考虑状态转移：一个格子可以由前一列格子的三个格子转移过来.
然后考虑如何表示那三列 开一个row数组，保存当前状态的上一列那三行，特判一下当前行是1或者是n然后修改对应的row数组值。
最后sort一下row数组，因为要得到字典序，所以从较小的数字（行数）开始枚举.
代码如下（过样例但是WA，日后再补吧呃呃呃）
#include
#include
#include
#include
#define INF (1
关注
打赏
![]()
1663570241
查看更多评论
最近更新
- 深拷贝和浅拷贝的区别（重点）
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state，props，refs（你学废了吗）
- 【脚手架VueCLI】从零开始，创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解（含代码）
- 【React】DOM的Diffing算法是什么？以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面？
