狗家 L4过经

感谢楼主 写的非常详细 想必代码功底一流

第一题有dp的解法但是不知道怎么generate sequence，有大佬知道怎么做吗

1. function racecarDP(target: number): number {
   
2.     const dp: number[] = Array(target + 1).fill(-1);
   
3.     return helper(target, dp);
   
4. }
   
5. 
   
6. function helper(target: number, dp: number[]): number {
   
7.     if (dp[target] >= 0) {
   
8.         return dp[target];
   
9.     }
   
10.     const n = Math.floor(Math.log2(target)) + 1;
    
11.     if (1 << n === target + 1) {
    
12.         dp[target] = n;
    
13.     } else {
    
14.         dp[target] = helper((1 << n) - 1 - target, dp) + n + 1;
    
15.         for (let m = 0; m < n - 1; m++) {
    
16.             dp[target] = Math.min(dp[target], helper(target - (1 << (n - 1)) + (1 << m), dp) + n + m + 1);
    
17.         }
    
18.     }
    
19.     return dp[target];
    
20. }

复制代码

为啥现在L4都没有design round了。。。

一样刚面完狗，希望来沾下喜气

微信用户_e7fb7bf 发表于 2022-4-30 12:24
第一题有dp的解法但是不知道怎么generate sequence，有大佬知道怎么做吗

所以可以用这个BFS记录sequence？