首页 > 编程语言 >代码随想录算法训练营第三十九天|Day39 动态规划

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

时间:2024-11-08 13:46:36浏览次数:3  
标签:numsSize Day39 int 金额 第三十九 随想录 amounts start dp

198.打家劫舍

视频讲解:https://www.bilibili.com/video/BV1Te411N7SX

https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html

思路

#define max(a, b) ((a) > (b) ? (a) : (b))
int rob(int* nums, int numsSize) {
    if(numsSize == 0){
        return 0;
    }
    if(numsSize == 1){
        return nums[0];
    }
    int dp[numsSize];
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for(int i = 2; i < numsSize; i++){
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[numsSize - 1];
}

​

学习反思

使用动态规划的思想来解决打家劫舍问题。首先定义了一个max宏来返回两个数中较大的一个。然后定义了一个dp数组,dp[i]表示在前i个房屋中能够偷到的最大金额。初始情况下,当只有一个房屋时,最大金额就是该房屋的金额。当有两个房屋时,最大金额为两个房屋金额的较大值。然后通过一个循环来计算每个房屋能够偷到的最大金额。对于第i个房屋,有两种选择:偷或者不偷。如果偷第i个房屋,则最大金额为dp[i-2]加上第i个房屋的金额;如果不偷第i个房屋,则最大金额为dp[i-1]。取这两个值中的较大值作为dp[i]的值。最后返回dp[numsSize-1],即在前numsSize个房屋中能够偷到的最大金额。该方法的时间复杂度为O(n)。

213.打家劫舍II

视频讲解:https://www.bilibili.com/video/BV1oM411B7xq

https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html

思路

#define max(a, b) ((a) > (b) ? (a) : (b))
int robRange(int* nums, int start, int end, int numsSize) {
    if (end == start) return nums[start];
    int dp[numsSize];
    dp[start] = nums[start];
    dp[start + 1] = max(nums[start], nums[start + 1]);
    for (int i = start + 2; i <= end; i++) {
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[end];
}
int rob(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    if (numsSize == 1) return nums[0];
    int result1 = robRange(nums, 0, numsSize - 2, numsSize); 
    int result2 = robRange(nums, 1, numsSize - 1, numsSize); 
    return max(result1, result2);
}

学习反思

首先定义了一个私有函数robRange,它的功能是求解在某个范围内房屋能够偷到的最大金额。robRange的参数包括nums数组、起始位置start、结束位置end以及数组长度numsSize。它的返回值是在[start, end]范围内能够偷到的最大金额。robRange的实现基本和原来的动态规划解法相同,只是将数组dp的大小改为了numsSize,并且只计算了在[start, end]范围内的结果。然后,在主函数rob中,首先处理特殊情况,当numsSize为0或1时,直接返回结果。然后调用robRange函数分别计算从第0个房屋到倒数第二个房屋和从第1个房屋到最后一个房屋能够偷到的最大金额。最后取这两个结果中的较大值作为最终的结果。这种分段处理的方式能够解决循环数组的问题,时间复杂度仍然是O(n)

337.打家劫舍III

视频讲解:https://www.bilibili.com/video/BV1H24y1Q7sY

https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html

思路

int *robTree(struct TreeNode *node) {
    int* amounts = (int*) malloc(sizeof(int) * 2);
    memset(amounts, 0, sizeof(int) * 2);
    if(node == NULL){
        return amounts;
    }
    int * left = robTree(node->left);
    int * right = robTree(node->right);
    amounts[1] = node->val + left[0] + right[0];
    amounts[0] = max(left[0], left[1]) + max(right[0], right[1]);
    return amounts;
}
int rob(struct TreeNode* root) {
    int * dp = robTree(root);
    return max(dp[0], dp[1]);
}

学习反思

函数robTree是递归函数,它接受一个树节点作为参数,返回一个包含两个元素的数组amounts,其中amounts[0]表示不打劫当前节点能获得的最大金额,amounts[1]表示打劫当前节点能获得的最大金额。首先,函数动态为amounts分配了一个包含两个元素的数组,并使用memset函数将数组初始化为0。接下来,如果当前节点node为空,则直接返回amounts。否则,函数递归地调用robTree函数,分别对左子树和右子树进行打劫操作,并将返回的结果保存在leftright指针中。然后,计算打劫当前节点的最大金额。根据题目要求,打劫当前节点时,不能打劫其直接相连的子节点。因此,打劫当前节点的最大金额等于当前节点的值加上左子树不打劫根节点的最大金额加上右子树不打劫根节点的最大金额。将这个值保存在amounts[1]中。接着,计算不打劫当前节点的最大金额。根据题目要求,不打劫当前节点时,可以选择打劫其直接相连的子节点。因此,不打劫当前节点的最大金额等于左子树的两种选择中的最大金额加上右子树的两种选择中的最大金额。将这个值保存在amounts[0]中。最后,返回amounts数组。函数rob是主函数,它调用robTree函数来计算二叉树中打劫的最大金额。首先,调用robTree函数得到一个包含两个元素的数组dp。然后,返回dp[0]dp[1]中的较大值作为结果。

总结

今天是打家劫舍的一天,这个系列不算难,加油!!!

标签:numsSize,Day39,int,金额,第三十九,随想录,amounts,start,dp
From: https://blog.csdn.net/a6666999d/article/details/143605151

相关文章

  • 代码随想录算法训练营第四十天|Day40 动态规划
    121.买卖股票的最佳时机视频讲解:https://www.bilibili.com/video/BV1Xe4y1u77qhttps://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html思路#definemax(a,b)((a)>(b)?(a):(b))#definemin......
  • 代码随想录算法训练营第二十天|leetcode235. 二叉搜索树的最近公共祖先、leetcode701.
    1leetcode235.二叉搜索树的最近公共祖先题目链接:235.二叉搜索树的最近公共祖先-力扣(LeetCode)文章链接:代码随想录视频链接:二叉搜索树找祖先就有点不一样了!|235.二叉搜索树的最近公共祖先_哔哩哔哩_bilibili思路:用之前一样的方法,哈哈哈哈哈,好处就是做出来了,但是我觉得需......
  • 代码随想录算法训练营第九天|LeetCode151.翻转字符串里的单词、卡码网:55.右旋转字符串
    前言打卡代码随想录算法训练营第49期第九天︿( ̄︶ ̄)︿首先十分推荐学算法的同学可以先了解一下代码随想录,可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解,卡哥清晰易懂的算法教学让我直接果断关注,也十分有缘和第49期的训练营大家庭一起进步。今日题目LeetCode151翻转字......
  • 代码随想录算法训练营 day37 day38| 卡码网52.完全背包 518. 零钱兑换 II 377.
    学习资料:https://programmercarl.com/背包问题理论基础完全背包.html#算法公开课相比于01背包,完全背包中每个物品都可以无限次的放入组合:先遍历物品,再逆序遍历背包排列:先逆序遍历背包,再遍历物品学习记录卡码网52.携带研究资料(dp[i]代表当重量为i时的最大价值)点击查看代码n......
  • 代码随想录一刷day7 哈希表day1
    遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。常见三种实现哈希表的数据结构:数组set集合map映射下面是setmap的红黑树是一种平衡二叉搜索树,所以k......
  • 代码随想录第七天|哈希表part02--454.四数相加II、383. 赎金信、15. 三数之和、18. 四
    资源引用:leetcode题目:454.四数相加Ⅱ(454.四数相加II-力扣(LeetCode))383.赎金信(383.赎金信-力扣(LeetCode))15.三数之和(15.三数之和-力扣(LeetCode))18.四数之和(18.四数之和-力扣(LeetCode))例行碎碎念:今天也追赶上了一些进度,虽然生病感冒,但今天很好的坚持了从早到晚......
  • 代码随想录算法训练营第十八天|leetcode530.二叉搜索树的最小绝对差、leetcode501.二
    1leetcode530.二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)文章链接:代码随想录视频链接:你对二叉搜索树了解的还不够!|LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili思路:定义一个极大值作为结果,然后在中序遍历过程中进行比较出结果1.1自己的......
  • 代码随想录打卡Day14
    1.力扣226:翻转二叉树题目描述:给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]解答代码:/***Definitionforabin......
  • 代码随想录打卡Day18
    1.二叉搜索树的最小绝对差:题目描述给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。示例1:输入:root=[4,2,6,1,3]输出:1代码:/***Definitionforabinarytreenode.*structTree......
  • 代码随想录打卡Day17
    1.力扣954:最大二叉树:题目描述:给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:创建一个根节点,其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右......