[leetcode]279. Perfect Squares -- JavaScript 代码

偏执的太偏执、 2022-07-19 02:42 142阅读 0赞 
  1. /** * @param {number} n * @return {number} */
  2. var numSquares = function(n) {
  3.     var squart_root = 1;
  4.     var dp = [];
  5.     for(var i = 1;i<n+1;i++){
  6.         if(i == squart_root*squart_root){
  7.             dp[i] = 1;
  8.             squart_root ++ ;
  9.         }else{
  10.             var min = i;
  11.             for(var j = squart_root-1;j>0;j--){
  12.                 min = Math.min(min,1+dp[i-j*j]);
  13.             }
  14.             dp[i] = min;
  15.         }
  16.     }
  17.     return dp[n];
  18. };

这道题的解题思路是动态规划。
求解答案需要从数字1开始一点点累加，最后才能得到结果。

发表评论

表情：
评论列表 （有 0 条评论，142人围观）

还没有评论，来说两句吧...

相关阅读