内容简介:今天在 leetcode 做动态规划的题, 做到一道整数划分的题目如下这个用动态规划很容易写出代码如下,后来想到, 这不就是均值不等式吗? 给定和, 求积最大, 即
今天在 leetcode 做动态规划的题, 做到一道整数划分的题目如下
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Example 1:
Input: 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1.
这个用动态规划很容易写出代码如下,
class Solution: def integerBreak(self, n): """ :type n: int :rtype: int """ self.dic={1:1} for i in range(2,n+1): mx = 1 for j in range(1,i): prod = j*self.dic[i-j] mx =max(mx,prod,j*(i-j)) self.dic[i] = mx return self.dic[n]
后来想到, 这不就是均值不等式吗? 给定和, 求积最大, 即
如果先不考虑整数的话,易知当所有数相等时最大,但是注意这里并不知道数的个数 k, 所以设各个数为 x, 有 n/x个
要求出 x, 可以用导数. 各个数的积即为 $x^{\frac{n}{x}}$, 求其最大值
求导得
易知当 x = e 的时候函数 f(x)有最大值
下面考虑整数, x=2 或者 3
即比较 $2^{\frac{n}{2}}$, $3^{\frac{n}{3}}$
的增长速度, 这很简单了, 其实都是指数函数, 换个形式即为
$\sqrt{2}^{n}$, $\sqrt[3]{3}^{n}$
由于 n > 0 , 底数大的增长快,
计算得
$\sqrt{2} = 1.414, \sqrt[3]{3} = 1.442$
所以, 尽量将整数 n 分成 3即可,
于是原题目有了下面的非动态规划解法
class Solution(object): def integerBreak(self, n): """ :type n: int :rtype: int """ if n<5: return [0, 0, 1, 2, 4][n] x = n % 3 if x == 0: return 3 ** (n // 3) if x == 1: return 3 ** (n // 3 - 1) * 4 return 3 ** (n // 3) * 2
本来是个很简单的题, 但是给我的感觉就是:
动态规划是种系统的方法, 它依靠计算机的算力对问题直接求解, 不用了解其背后的数学原理.
而有时候, 如果我们跳出常规思维, 思考问题背后的数学规律, 就可能发现更加好的解法. 更加完备,快速, 健壮.
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 如何划分限界上下文
- 如何给 Hadoop 集群划分角色
- 【LeetCode】贪心算法--划分字母区间(763)
- JVM笔记-运行时内存区域划分
- Python列表推导式一则:等价类划分
- 简单解决大型 Flask 蓝图的路由划分
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
学习JavaScript数据结构与算法(第2版)
[巴西] Loiane Groner / 邓 钢、孙晓博、吴 双、陈 迪、袁 源 / 人民邮电出版社 / 2017-9 / 49.00元
本书首先介绍了JavaScript 语言的基础知识以及ES6 和ES7 中引入的新功能,接下来讨论了数组、栈、队列、链表、集合、字典、散列表、树、图等数据结构,之后探讨了各种排序和搜索算法,包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序、顺序搜索、二分搜索,然后介绍了动态规划和贪心算法等常用的高级算法以及函数式编程,最后还介绍了如何计算算法的复杂度。一起来看看 《学习JavaScript数据结构与算法(第2版)》 这本书的介绍吧!