网站开发页面设计过程,做个人网页,网站维修合同,免费又实用的网站343. 整数拆分 题目链接#xff1a;link 文章讲解#xff1a;link 视频讲解#xff1a;link 一、做题感受第一想法
其实第一反应是回溯……但感觉每层的集合都会很繁琐
二、学习文章后收获
1.动态规划思路 动规五要素分析 dp和i的定义#xff1a;dp[i]指把i拆分后最…343. 整数拆分 题目链接link 文章讲解link 视频讲解link 一、做题感受第一想法
其实第一反应是回溯……但感觉每层的集合都会很繁琐
二、学习文章后收获
1.动态规划思路 动规五要素分析 dp和i的定义dp[i]指把i拆分后最大乘积所以dp[1]、dp[0]都没有太大意义因为0和1拆了乘积也是0递归公式dp[i] max(j * (i - j) , j * dp[i - j]), 1 j i - 1ji-1是为什么因为j i-1时dp[j-i]也就是dp[1]为0没有意义而 j*(i-j)也就是i-1*1这和 j1重复了所以可以省去j i-1的讨论初始化dp[0] 0dp[1] 0dp[2] 1遍历顺序从前往后手算序列略 递归公式的说明求dp[i]可分成两种情况 把 i 拆成 j 和 i - j 两个数总共两个数。把 i 拆成 j 和和为 i - j 的若干个数总共大于等于三个数。
class Solution {
public:int integerBreak(int n) {vectorint dp(n1,0); //dp[i]:拆分i得到的最大乘积dp[0] 0;dp[1] 0; //其实这俩初始化无所谓因为没有意义dp[2] 1; // 1*1for(int i 3;i n;i){for(int j 1;j i - 1;j){dp[i] max(dp[i],max(j*(i-j),j*dp[i-j]));}}return dp[n];}
};2.动态规划优化
思路for循环上的剪枝剪枝依据是要想找到乘积最大的拆分方式需要让拆出来的所有数字尽可能大小相似。所以对于太大的 j 可以直接跳过。 故内层for的条件改为 j i/2for (int j 1; j i / 2; j)
class Solution {
public:int integerBreak(int n) {vectorint dp(n 1);dp[2] 1;for (int i 3; i n ; i) {for (int j 1; j i / 2; j) { //heredp[i] max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n];}
};
2.贪心思路
思路本题也可以用贪心每次拆成n个3如果剩下是4则保留4然后相乘但是这个结论需要数学证明其合理性
此处没有证明而是直接用了结论。
说明 if(n 2) return 1; if(n 3) return 2; if(n 4) return 4; 剩下的拆成3的和直到剩下4或者不足3也就是前面是一堆3最后剩下的值4即停止作为最后一个数字。
class Solution {
public:int integerBreak(int n) {if(n 1 || n 0) return 0;if(n 2) return 1;if(n 3) return 2;if(n 4) return 4;int remains n - 3,result 3;while(remains 4){result * 3;remains - 3;}result * remains;return result;}
};三、过程中遇到的问题
1.多个数取最大
max(a,max(b,c)) 96.不同的二叉搜索树 题目链接link 文章讲解link 视频讲解link 一、做题感受第一想法
动规五要素分析 dp和i的定义dp[i]指 i 个节点的二叉搜索树共有多少种树型递归公式dp[i] dp[j] * dp[i-j-1], 0 j i - 1左子树 j 个节点右子树 i - j - 1个节点。总树型为 左子树的树型数 乘以 右子树的树型数初始化dp[0] 1dp[1] 1遍历顺序从前往后手算序列略
class Solution {
public:int numTrees(int n) {vectorint dp(n1,0);dp[0] 1;dp[1] 1;for(int i 2;i n;i){ //dp[i]for(int j 0;j i - 1;j){ //左子树j右子树i-j-1dp[i] dp[j] * dp[i-j-1]; //递推公式}}return dp[n];}
};
