dtcms 源码 gps VBA regex flexbox textview xsd vue修改样式 pmp教学视频 nginx教程视频 一兆等于多少字节 pr序列设置哪个好 java解析json数组 edate函数的使用方法 mysql重启 docker启动命令 python基础 python3入门 java求和 java怎么配置 java时间格式化 java怎么输出数组 java程序设计教程 街头篮球辅助 手机照片恢复免费软件 din字体下载 地球末日攻略 java电子书 JScodeblocks汉化包 掌门一对一下载 华为动态照片 cinema4d下载 jpg格式转换器 fireworks序列号 调试js lol不能全屏 速查表 小米手机开发者模式 ie内核修复 金万维动态域名
当前位置: 首页 > 学习教程  > 编程语言

279. 完全平方数

2020/11/4 14:49:51 文章标签:

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n 12 输出: 3 解释: 12 4 4 4. 示例 2: 输入: n 13 输出: 2 解释: 13 4 9. 令dp[i]为组成…

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.
示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

令dp[i]为组成和i的完全平方数的最小个数

那么,有i - j*j + j*j = i,dp[i-j*j] + 1是可能的答案

dp[i] = min(dp[i-j*j]) + 1, j*j<=i

class Solution {
public:
    int numSquares(int n) {
        int *dp = new int[n + 1]();
        for(int i = 1; i <= n; i++)
        {
            int minn = INT_MAX;
            for(int j = 1; j * j <= i; j++)
            {
                minn = min(minn, dp[i - j * j]);
            }
            dp[i] = minn + 1;
        }
        return dp[n];
    }
};

 


本文链接: http://www.dtmao.cc/news_show_350225.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?