【动态规划专题】剑指 Offer 49. 丑数

共以下 1 个回答

• 塔底的仰望 永久会员 2023年9月14日 下午10:52

  时间复杂度O(n); 空间复杂度O(n)

  class Solution {
      public int nthUglyNumber(int n) {
          int a = 1, b = 1, c = 1;
          int[] dp = new int[n+1];
          dp[1] = 1;
  
          for(int i = 2; i <= n; i++) {
              dp[i] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
              if (dp[i] == dp[a] * 2) {
                  a++;
              }
              if (dp[i] == dp[b] * 3) {
                  b++;
              }
              if (dp[i] == dp[c] * 5) {
                  c++;
              }
          }
  
          return dp[n];
      }
  }
  

  0 赞同 0 条回复

  登录以回复