动态规划
定义:通过把原问题分解成多个子问题来解决复杂问题的方法;
解释:动态规划用于解决重叠子问题和最优子结构的问题。
思想:若要解决一个问题,我们需要解其不同部分,再根据子问题的解得出原问题的解。通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量;一旦某个给定子问题的解已经算出,就将其记忆化存储,以便下次需要同一个子问题解时直接查表。这种方法在重复子问题的数目关于输入的规模呈指数增长时特别有用
整数拆分
题目:给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
以6为例子:
这个问题我们就可以用动态规划法来解决;
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
let dp = new Array(n+1);
dp[1] = 1;
dp[2] = 1;
for(let i= 3; i <= n ; i++){
// 从小到大计算出每个dp的值
dp[i] = 0;
for(let j = 1; j<= i-j ; j++){
// j*(i-j) 不拆分i-j
// j*dp[i-j] 继续对i-j进行拆分,
// dp[i-j]已经在之前的计算中计算过了,不必重复计算
dp[i] = Math.max(dp[i], j*(i-j), j*dp[i-j])
}
}
return dp[n]
};
当我们不再需要外在的认可来证明自己时
才能获得真正的自由