HDU 2686矩阵问题如何运用双线程动态规划解决？

本文共计884个文字，预计阅读时间需要4分钟。

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2686题目内容：从矩阵的（1,1）到（n,n）再从（n,n）到（1,1）中间不经过重复的值，来回来能走过的最大值是多少？思路：打一个来回可以想象成从（1,1）到（n,n）再到（1,1）的路径，我们可以使用动态规划来解决这个问题。定义dp[i][j]为从（1,1）到（i,j）的最小值，那么dp[n][n]就是我们要找的答案。状态转移方程为dp[i][j]=min(dp[i-1][j], dp[i][j-1]) + 1，其中1表示从（i-1,j）或（i,j-1）到（i,j）需要走的步数。初始化dp[1][1]=0，dp[i][1]=i-1，dp[1][j]=j-1。