• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

字节跳动面试题:动态规划

开发技术 开发技术 2周前 (04-07) 5次浏览

题目

一个环有0~9十个点,起点为原点,每步向左或向右一步,问k步返回原点的走法n

解法:动态规划

状态:dp(k,j): 表示从点 j 走 k 步到达原点 0 的方法数

所以是一个二维的动态规划

从第k-1步到第k步有动态转移方程:dp(kjdp(k1j1dp(k1j+1)

考虑到是环的问题,改成:dp(kjdp(k1(j1+n)%ndp(k1(j+1)%n)

因此时间复杂度是O(k*n)

考虑到dp(k) 只与dp(k-1)有关 ,所以空间复杂度O(n)就够了

 

 

 

参考链接:(代码也参考此链接)

https://blog.csdn.net/weixin_41888257/article/details/108705557

 

 


程序员灯塔
转载请注明原文链接:字节跳动面试题:动态规划
喜欢 (0)