动态规划，求解《面试题 17.09. 第 k 个数》

var getKthMagicNumber = function(k) {
  const dp = new Array(k), primes = [3n, 5n, 7n], p = new Uint32Array(3)
  dp[0] = 1n
  for (let i = 1; i < k; i++) {
    let minProduct = Infinity, minIndexs = []
    for (let j = 0; j < 3; j++) {
      const product = primes[j] * dp[p[j]]
      if (product < minProduct) {
        minProduct = product
        minIndexs = [j]
      } else if (product === minProduct) minIndexs.push(j)
    }
    dp[i] = minProduct
    for (let i = 0; i < minIndexs.length; i++) p[minIndexs[i]]++
  }
  return dp[k - 1]
};

function getKthMagicNumber(k: number): number {
  const dp = new Array(k), primes = [3n, 5n, 7n], p = new Uint32Array(3)
  dp[0] = 1n
  for (let i = 1; i < k; i++) {
    let minProduct = BigInt(1e32), minIndexs = []
    for (let j = 0; j < 3; j++) {
      const product = primes[j] * dp[p[j]]
      if (minProduct > product) {
        minProduct = product
        minIndexs = [j]
      } else if (minProduct === product) minIndexs.push(j)
    }
    dp[i] = minProduct
    for (let i = 0; i < minIndexs.length; i++) p[minIndexs[i]]++
  }
  return dp[k - 1]
};

class Solution {
  function getKthMagicNumber($k) {
    $dp = array_fill(0, $k, 0);
    $primes = [3, 5, 7];
    $p = array_fill(0, 3, 0);
    $dp[0] = 1;
    for ($i = 1; $i < $k; $i++) {
      $minProduct = PHP_INT_MAX;
      $minIndexs = [];
      for ($j = 0; $j < 3; $j++) {
        $product = $primes[$j] * $dp[$p[$j]];
        if ($minProduct > $product) {
          $minProduct = $product;
          $minIndexs = [$j];
        } else if ($minProduct === $product) $minIndexs []= $j;
      }
      $dp[$i] = $minProduct;
      foreach ($minIndexs as $minIndex) $p[$minIndex]++;
    }
    return $dp[$k - 1];
  }
}

func getKthMagicNumber(k int) int {
  dp, primes, p  := make([]int, k), []int{3, 5, 7}, []int{0, 0, 0}
  dp[0] = 1
  for i := 1; i < k; i++ {
    minProduct, minIndexs := int(^uint(0) >> 1), []int{}
    for j := 0; j < 3; j++ {
      product := primes[j] * dp[p[j]]
      if minProduct > product {
        minProduct = product
        minIndexs = []int{j}
      } else if minProduct >= product {
        minIndexs = append(minIndexs, j)
      }
    }
    dp[i] = minProduct
    for _, minIndex := range minIndexs {
      p[minIndex]++
    }
  }
  return dp[k - 1]
}

class Solution {
  public int getKthMagicNumber(int k) {
    long[] dp = new long[k];
    int[] p = new int[3], primes = new int[]{3, 5, 7};
    dp[0] = 1;
    for (int i = 1; i < k; i++) {
      long minProduct = Long.MAX_VALUE;
      List<Integer> minIndexs = new ArrayList<Integer>();
      for (int j = 0; j < 3; j++) {
        long product = primes[j] * dp[p[j]];
        if (minProduct > product) {
          minProduct = product;
          minIndexs.clear();
          minIndexs.add(j);
        } else if (minProduct == product) {
          minIndexs.add(j);
        }
      }
      dp[i] = minProduct;
      for (int minIndex : minIndexs) p[minIndex]++;
    }
    return (int)dp[k - 1]; // 正确值应返回 long，转为 int 是为了匹配题目返回值类型要求
  }
}

public class Solution {
  public int GetKthMagicNumber(int k) {
    int[] dp = new int[k], primes = new int[]{3, 5, 7}, p = new int[]{0, 0, 0};
    dp[0] = 1;
    for (int i = 1; i < k; i++) {
      int minProduct = int.MaxValue;
      IList<int> minIndexs = new List<int>();
      for (int j = 0; j < 3; j++) {
        int product = primes[j] * dp[p[j]];
        if (product < minProduct) {
          minProduct = product;
          minIndexs.Clear();
          minIndexs.Add(j);
        } else if (product == minProduct) {
          minIndexs.Add(j);
        }
      }
      dp[i] = minProduct;
      foreach (int minIndex in minIndexs) p[minIndex]++;
    }
    return dp[k - 1];
  }
}

int getKthMagicNumber(int k){
  int* dp = malloc(sizeof(int) * k);
  int* p = malloc(sizeof(int) * 3);
  memset(p, 0, sizeof(int) * 3);
  int* primes = malloc(sizeof(int) * 3);
  primes[0] = 3;
  primes[1] = 5;
  primes[2] = 7;
  dp[0] = 1;
  for (int i = 1; i < k; i++) {
    int minProduct = INT_MAX;
    int* minIndexs = malloc(sizeof(int) * 1e3);
    int minPos = 0;
    for (int j = 0; j < 3; j++) {
      int product = primes[j] * dp[p[j]];
      if (product < minProduct) {
        minProduct = product;
        minPos = 1;
        minIndexs[0] = j; 
      } else if (product == minProduct) {
        minIndexs[minPos++] = j;
      }
    }
    dp[i] = minProduct;
    for (int i = 0; i < minPos; i++) p[minIndexs[i]]++;
  }
  return dp[k - 1];
}

class Solution {
public:
  int getKthMagicNumber(int k) {
    vector<int> dp(k), primes = {3, 5, 7}, p = {0, 0, 0};
    dp[0] = 1;
    for (int i = 1; i < k; i++) {
      int minProduct = INT_MAX;
      vector<int> minIndexs;
      for (int j = 0; j < 3; j++) {
        int product = primes[j] * dp[p[j]];
        if (minProduct > product) {
          minProduct = product;
          minIndexs.clear();
          minIndexs.push_back(j);
        } else if (minProduct == product) {
          minIndexs.push_back(j);
        }
      }
      dp[i] = minProduct;
      for (int minIndex : minIndexs) p[minIndex]++;
    }
    return dp[k - 1];
  }
};

class Solution:
  def getKthMagicNumber(self, k: int) -> int:
    dp, primes, p = [0] * k, [3, 5, 7], [0] * 3
    dp[0] = 1
    for i in range(1, k):
      minProduct, minIndexs = sys.maxsize, list()
      for j in range(0, 3):
        product = primes[j] * dp[p[j]]
        if minProduct > product: minProduct, minIndexs = product, [j]
        elif minProduct == product: minIndexs.append(j)
      dp[i] = minProduct
      for minIndex in minIndexs: p[minIndex] += 1
    return dp[k - 1]