CSMania

You may say I'm a Programmer, but I'm not the only one

代码随想录算法训练营第四十八天| 动态规划

121. 买卖股票的最佳时机 这道题还是挺简单的，一下子就做出来的。 class Solution { public: int maxProfit(vector<int>& prices) { vector<int> dp(prices.size(),0); int min_price = prices[0]; ...

Posted by Zhuoqun on March 2, 2023

代码随想录算法训练营第四十七天| 动态规划

198.打家劫舍 终于没借助任何提示，自己写出来了。 class Solution { public: int rob(vector<int>& nums) { vector<int> dp (nums.size()+1,0); dp[0] = 0; dp[1] = nums[0]; f...

Posted by Zhuoqun on March 1, 2023

代码随想录算法训练营第四十六天| 动态规划

139.单词拆分 没想到怎么用动态规划去写，看题解说回溯算法也能做，就自己写了回溯算法的。但是超时了。 class Solution { public: static bool cmp(string a, string b){ if(a.length() < b.length()) return true; return ...

Posted by Zhuoqun on February 28, 2023

代码随想录算法训练营第四十五天| 动态规划

70. 爬楼梯 （进阶） class Solution { public int climbStairs(int n) { int[] dp = new int[n + 1]; int[] weight = {1,2}; dp[0] = 1; for (int i = 0; i <= n; i++) { ...

Posted by Zhuoqun on February 27, 2023

代码随想录算法训练营第四十五天| 动态规划

70. 爬楼梯 （进阶） class Solution { public int climbStairs(int n) { int[] dp = new int[n + 1]; int[] weight = {1,2}; dp[0] = 1; for (int i = 0; i <= n; i++) { ...

Posted by Zhuoqun on February 27, 2023

代码随想录算法训练营第四十四天| 动态规划

518. 零钱兑换 II 真是不太明白 class Solution { public: int change(int amount, vector<int>& coins) { int coin_size = coins.size(); vector<int> dp(amount+1,0); dp[0...

Posted by Zhuoqun on February 26, 2023

代码随想录算法训练营第四十二天| 动态规划

1049. 最后一块石头的重量 II 这道题仅仅是理解了。还有问题没想明白： 为什么求总和的平均值就可以了？不会出现两边石头数量不对等，导致碰撞后的情况不是sum-dp[target]*2的情况吗？ dp的大小设成15000就可以，还是一定要150001？因为我跑15000的时候，也没有报错 class Solution { public: int lastStoneWe...

Posted by Zhuoqun on February 24, 2023

代码随想录算法训练营第四十一天| 动态规划

416. 分割等和子集 01背包问题的二维数组版弄懂了，一维数组的还是不清楚为什么要倒叙。 class Solution { public: bool canPartition(vector<int>& nums) { if(nums.size() == 1){ return false; } ...

Posted by Zhuoqun on February 23, 2023

代码随想录算法训练营第四十天天| 动态规划

343. 整数拆分 这道题感觉是融合了贪心算法和动态规划。我自己想了一早上也没想出来该怎么写，看了Carl的解题思路也没自己写出来。但现在是懂了。 这道题其实就是把n拆分成小份，算每个小份的最大值是多少。这个概念好理解，但是如何将这个概念用程序表示出来很难，需要用双层for loop去做。第一层，也就是i，它是首先从数值3开始，把从n若是等于3时的结果算出来，记录到dp数组了。然后再算n等...

Posted by Zhuoqun on February 22, 2023

代码随想录算法训练营第三十九天| 动态规划

62.不同路径 这道题之前做过，有印象，所以自己能写出来。但是在2d vector初始化的时候写的格式不对。其实可以直接用2d int来做的，不一定非要用vector。思维僵化了。 class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m,...

Posted by Zhuoqun on February 21, 2023

FEATURED TAGS
读书笔记 刷题录
ABOUT ME

Loving Programming & Wrestling

✉️ gavinlizhuoqun@gmail.com