每日leetcode第0081天 0935. Knight Dialer

欢迎来到骑士拨号器。

这是一道很有趣的看上去像二维数组矩阵,实际上完全不用模拟的题。

这道题我们需要用到的是动态规划。

一个点可以去另两个点,那么这个点也只能从那两个点过来。

所以我们可以建立一个二维数组phone_numbers[i][j],其中i代表走几步,j代表最终走到的数字,值表示电话号码的可能性有多少种。

状态转移方程式则为:……

天那,写状态转移时候写疯我了,我要根据j来判断怎么转换,我一开始本能用if,后来发现0-9有10个,应该用switch。当我写完switch我发现全部都是要走一遍的,压根不用判断j,就写它个十行状态转移方程式,这样内层循环都省了。

最终把10个数字的方案加总,输出。

这里注意会一直做module1000000007的操作,所以用int也行。毕竟两个小于10亿的数字加起来也超不过21个亿。

这道题还有别的思路,就是根据号码的对称性来分类,这样算前算后乘一下对称的号码数量也可以。可以少算一点点,不太多。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。