leetcode-hot100-15动态规划

4.动态规划文章目录4.动态规划70.爬楼梯方法一：c方法一：js方法一：java118. 杨辉三角方法一：c方法一：js方法一：java198. 打家劫舍方法一：c方法一：js方法一：java279. 完全平方数方法一：c方法一：js方法一：java322. 零钱兑换方法一：c方法一：js方法一：java139. 单词拆分方法一：c方法一：js方法一：java300. 最长递增子序列方法一：c方法一：js方法一：java152. 乘积最大子数组方法一：c方法一：js方法一：java416. 分割等和子集方法一：c方法一：js方法一：java32. 最长有效括号方法一：c方法一：js方法一：java方法二（栈）：c方法二：js方法二：java70.爬楼梯假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶方法一：c状态标识：爬到第i层楼梯时，有多少种方法。状态转移方程：dp[i] = dp[i-1] + dp[i-2]，表示从走一步和走两步的方式。初始化：dp[1] = 1 , dp[2] = 2。返回值：dp[n]，即走到第n层可以有多少种爬法。class Solution{public:intclimbStairs(intn){intdp[50]={0,1,2};// 定义dp数组，dp[0]=0（占位），dp[1]=1（1阶1种），dp[2]=2（2阶2种）for(inti=3;i=n;++i)// 从第3阶开始递推到目标n阶{dp[i]=dp[i-1]+dp[i-2];// 状态转移：到达i阶 = i-1阶走1步 + i-2阶走2步}returndp[n];// 返回爬到n阶的总方法数}};方法一：jsvarclimbStairs=function(n){letdp=newArray(50).fill(0);// 创建长度50的dp数组，初始全部填充0dp[0]=0;// 0阶无意义，占位使用dp[1]=1;// 1阶楼梯：1种爬法dp[2]=2;// 2阶楼梯：2种爬法for(leti=3;i=n;i++){// 从3阶开始遍历到目标n阶dp[i]=dp[i-1]+dp[i-2];// 动态规划核心：当前方法数 = 前一阶 + 前两阶方法数}returndp[n];// 返回n阶楼梯的总攀爬方法数};方法一：javaclassSolution{publicintclimbStairs(intn){int[]dp=newint[50];// 创建长度为50的dp数组，存储每阶楼梯的方法数dp[0]=0;// dp[0]无实际意义，仅作为占位初始化dp[1]=1;// 1阶楼梯只有1种爬法dp[2]=2;// 2阶楼梯有2种爬法for(inti=3;i=n;i++){// 循环从3阶开始递推计算dp[i]=dp[i-1]+dp[i-2];// 递推公式：当前方法数 = 前一阶 + 前两阶方法数之和}returndp[n];// 返回n阶对应的总爬法数量}}118. 杨辉三角给定一个非负整数 *numRows，*生成「杨辉三角」的前numRows行。在**「杨辉三角」**中，每个数是它左上方和右上方的数的和。输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]就是一道找规律的题目，每一列第一个和每一行最后一个初始化为1，其余的为左上方和右上方数之和。状态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j-1]。方法一：cclass Solution{public:vectorvectorintgenerate(intnumRows){vectorvectorintdp(numRows);// 定义二维dp数组，行数为numRows，存储杨辉三角for(inti=0;inumRows;++i)// 遍历每一行i，从第0行开始dp[i].resize(i+1),dp[i][i]=1,dp[i][0]=1;// 每行扩容为i+1列，首尾元素赋值为1for(inti=2;inumRows;++i)// 从第2行开始计算中间值（前两行已初始化）for(intj=1;ji;++j)// 遍历每行中间位置j（非首尾）dp[i][j]=dp[i-1][j]+dp[i-1][j-1];// 核心公式：当前值=上一行同列+上一行前一列returndp;// 返回生成好的杨辉三角二维数组}};vector.resize(n)：修改容器实际有效元素个数 / 长度，分配空间并初始化；区别：reserve(n)只预存容量、不改元素个数。方法一：jsvargenerate=function(numRows){letdp=newArray(numRows);// 创建二维数组，行数为numRows，对应C++ dp数组for(leti=0;inumRows;i++){// 遍历每一行idp[i]=newArray(i+1).fill(1);// 每行创建i+1长度数组，全部初始化为1（首尾为1）}for(leti=2;inumRows;i++){// 从第2行开始计算中间元素for(letj=1;ji;j++){// 遍历中间列jdp[i][j]=dp[i-1][j]+dp[i-1][j-1];// 杨辉三角核心公式赋值}}returndp;// 返回生成的杨辉三角};方法一：javaclassSolution{publicListListIntegergenerate(intnumRows){ListListIntegerdp=newArrayList();// 创建集合存储杨辉三角，对应C++的vector二维数组for(inti=0;inumRows;i++){// 遍历每一行iListIntegerrow=newArrayList();// 创建当前行的集合for(intj=0;j=i;j++)row.add(1);// 初始化当前行所有元素为1，对应首尾赋值dp.add(row);// 将当前行加入总集合}for(inti=2;inumRows;i++){// 从第2行开始遍历计算中间值for(intj=1;ji;j++){// 遍历每行中间位置jdp.get(i).set(j,dp.get(i-1).get(j)+dp.get(i-1).get(j-1));// 赋值：上一行同列+上一行前一列}}returndp;// 返回最终杨辉三角}}198. 打家劫舍你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。方法一：c状态表示：dp[i]表示偷窃到第 i 家时，此时偷取到的最大金额。转移方程：dp[i] = max(dp[i-1] , dp[i-2] + num[i-1]) 初始化：dp[0] = nums[1]，第一家是可以直接偷取到的。 返回值：返回dp[n]，即偷取到最后一家是此时的最大金额。class Solution{public:introb(vectorintnums){intn=nums.size();// 获取房屋数量nvectorintdp(n+1,0);// 创建dp数组，dp[i]表示前i间房能偷的最大金额，初始全0dp[1]=nums[0];// 只有1间房时，最大金额就是第一间房的钱for(inti=2;i=n;++i)// 从第2间房开始遍历dp[i]=max(dp[i-1],dp[i-2]+nums[i-1]);//核心:不偷当前房=dp[i-1]，偷当前房=dp[i-2]+当前房钱，取最大值returndp[n];// 返回n间房的最大可偷金额}};1.dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);选择 A：不偷第 i 间那最大值 =前 i-1 间的最大值对应：dp[i-1]选择 B：偷第 i 间既然偷了第 i 间，就不能偷第 i-1 间最大值 =前 i-2 间最大值 + 第 i 间的钱对应：dp[i-2] + nums[i-1]最终 dp [i] 等于什么？A 和 B 里选更大的那个！方法一：jsvarrob=function(nums){letn=nums.length;// 获取房屋数量nletdp=newArray(n+1).fill(0);// 创建dp数组，长度n+1，全部初始化为0dp[1]=nums[0];// 只有1间房时，最大金额为第一间房的金额for(leti=2;i=n;i++)// 从第2间房开始遍历dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);// 动态规划核心：不偷/偷当前房取最大值returndp[n];// 返回n间房能偷的最大总金额};方法一：javaclassSolution{publicintrob(int[]nums){intn=nums.length