jd1*_*510 1 algorithm dynamic-programming
问题是如果只能以两种方式移动,找到从(1,1)(如果存在)到达(m,n)所需的最小步骤数的路径:(x,y)=(x + y,y)或(x,y)=(x,x + y).
我尝试用动态编程来做这个,但是m和n最多可以达到10 ^ 25,所以这是不可行的.如何调整我的解决方案以使其适用于大量输入？还是有其他方法吗？
use*_*ica 5
倒退.说你的目标是(x,y).如果x> y,则最后一步必须来自(x - y,y); 否则,最后一步必须来自(x,y - x).(如果x = y,则此位置无法访问.)向后工作时,很容易看到只有一种方法可以到达任何可到达的目标位置,并且该路径始终是显而易见的.
考虑到这一点,您可以使用欧几里德算法的微小变化来解决此问题.每个迭代或递归级别表示给定方向上的多个步骤,您可以跟踪沿途所需的步骤数.
归档时间：
9 年，2 月 前
查看次数：
114 次
最近记录：