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

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

时间:2024-11-01 17:19:31浏览次数:3  
标签:initDP int E5% 路径 随想录 Day33 ++ dp 第三十三

62.不同路径

https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html

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

思路

int **initDP(int m, int n) {
    int **dp = (int**)malloc(sizeof(int *) * m);
    int i, j;
    for(i = 0; i < m; ++i) {
        dp[i] = (int *)malloc(sizeof(int) * n);
    }
    for(i = 0; i < m; ++i)
        dp[i][0] = 1;
    for(j = 0; j < n; ++j)
        dp[0][j] = 1;
    return dp;
}

int uniquePaths(int m, int n){
    int **dp = initDP(m, n);
    int i, j;
    for(i = 1; i < m; ++i) {
        for(j = 1; j < n; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    int result = dp[m-1][n-1];
    free(dp);
    return result;
}

学习反思

主要实现了一个计算从起点到终点的唯一路径数的函数uniquePaths。通过动态规划的思想,利用一个二维数组来保存到达每个位置的路径数。函数initDP用于初始化一个大小为m*n的动态规划数组dp,并将起点位置的路径数初始化为1。函数uniquePaths先调用initDP初始化dp数组,然后通过两个for循环遍历dp数组,根据动态规划的递推公式计算每个位置的路径数。最后返回终点位置的路径数,同时释放掉dp数组的内存。时间复杂度为O(mn),空间复杂度为O(mn)。

63. 不同路径 II

https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.htmlhttps://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html

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

思路

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int m = obstacleGridSize;
    int n = obstacleGridColSize[0];
    int *dp = (int*)malloc(sizeof(int) * n);
    int i, j;
    for (j = 0; j < n; ++j) {
        if (obstacleGrid[0][j] == 1)
            dp[j] = 0;
        else if (j == 0)
            dp[j] = 1;
        else
            dp[j] = dp[j - 1];
    }

    for (i = 1; i < m; ++i) {
        for (j = 0; j < n; ++j) {
            if (obstacleGrid[i][j] == 1)
                dp[j] = 0;
            else if (j != 0)
                dp[j] += dp[j - 1];
        }
    }

    return dp[n - 1];
}

学习反思

在原有的uniquePaths基础上,添加了一个障碍物的判断条件。obstacleGrid是一个二维数组,表示地图,其中1表示障碍物,0表示可通行的路径。函数uniquePathsWithObstacles通过动态规划的思想,利用一个一维数组dp来保存到达每个位置的路径数。首先,根据障碍物的情况初始化第一行的路径数,如果遇到障碍物,则该位置的路径数为0,否则,第一行的路径数与前一个位置的路径数相同。然后,从第二行开始遍历,对于每个位置,如果遇到障碍物,则将该位置的路径数设为0;否则,将该位置的路径数更新为前一个位置的路径数与当前位置的路径数之和。最后,返回dp数组的最后一个元素,即终点位置的路径数。时间复杂度为O(m*n),空间复杂度为O(n)。

343.整数拆分

https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html

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

思路

int *initDP(int num) {
    int* dp = (int*)malloc(sizeof(int) * (num + 1));
    int i;
    for(i = 0; i < num + 1; ++i) {
        dp[i] = 0;
    }
    return dp;
}
int max(int num1, int num2, int num3) {
    int tempMax = num1 > num2 ? num1 : num2;
    return tempMax > num3 ? tempMax : num3;
}
int integerBreak(int n){
    int *dp = initDP(n);
    dp[2] = 1;
    int i;
    for(i = 3; i <= n; ++i) {
        int j;
        for(j = 1; j < i - 1; ++j) {      
            dp[i] = max(dp[i], j * (i - j), j * dp[i - j]);
        }
    }
    return dp[n];
}

学习反思

动态规划的例子,用于解决整数拆分问题。给定一个正整数n,拆分成至少两个正整数的和,并使得拆分后的正整数的乘积最大。函数integerBreak返回拆分后的正整数的乘积的最大值。函数initDP用于初始化一个大小为num + 1的数组dp,并将所有元素初始化为0。函数max用于返回三个数中的最大值。函数integerBreak通过动态规划的思想,遍历从3到n的所有整数,对于每个整数i,遍历从1到i - 1的所有整数j,并更新dp[i]的值。dp[i]的值表示将整数i拆分后的最大乘积。对于每个整数i,计算j * (i - j)以及j * dp[i - j]的最大值,并将其与dp[i]的值比较,更新dp[i]的值。最后,返回dp[n]的值,即拆分后的正整数的乘积的最大值。该代码的时间复杂度为O(n^2),空间复杂度为O(n)。

总结

动态规划,加油!!!

标签:initDP,int,E5%,路径,随想录,Day33,++,dp,第三十三
From: https://blog.csdn.net/a6666999d/article/details/143435140

相关文章

  • 代码随想录刷题学习日记
    仅为个人记录复盘学习历程,解题思路来自代码随想录代码随想录刷题笔记总结网址:代码随想录404.左叶子之和计算给定二叉树的所有左叶子之和。(所有的左边的叶子节点的和)提供参数:根结点root关键思路:遍历,判断若为左叶子节点,则将值累加。主要操作:递归三要素1.返回值类型和参......
  • 02链表算法/代码随想录
    前几天忙比赛,算法停了三天,继续开刷,不能停!!二、链表2.1删除链表中的元素两种方案无哨头:要删除节点的前一个结点指向删除节点的指向节点。头节点需要单独定义有哨头:头节点不需要单独定义实战力扣203/***Definitionforsingly-linkedlist.*publicclassLis......
  • 代码随想录一刷Day4
    59.螺旋矩阵II思路:找模式:1.从左到右,从上到下,从右到左,从下到上2.转几圈3.注意跟二分一样,统一原则4.注意for里面的循环条件54.螺旋矩阵思路:不能套用螺旋矩阵2 如果在此上进行修改,会漏很多情况动态移动上下边界  注意边界条件,这个需要<=,推一下便知 后面两题前缀......
  • 代码随想录之链表刷题总结
    目录1.链表理论基础2.移除链表元素3.设计链表4.翻转链表5.两两交换链表中的节点6.删除链表中的第N个节点7.链表相交8.环形链表1.链表理论基础链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后......
  • 代码随想录刷题学习日记
    仅为个人记录复盘学习历程,解题思路来自代码随想录代码随想录刷题笔记总结网址:代码随想录257.二叉树的所有路径给定一个二叉树,返回所有从根节点到叶子节点的路径。提供参数:根结点root关键思路:由于需要返回从根节点到叶子节点的路径,故采用前序遍历,每次遍历时将当前节点加......
  • 代码随想录算法训练营day31| 56. 合并区间 738.单调递增的数字
    学习资料:https://programmercarl.com/0056.合并区间.html#算法公开课贪心PART5over学习记录:56.合并区间(也是找重叠区间,但是是跟result[-1]比,只用比右边界;更新result[-1][1]为更大值)点击查看代码classSolution(object):defmerge(self,intervals):"""......
  • 代码随想录算法训练营第十二天| 226.翻转二叉树、101. 对称二叉树、104.二叉树的最大
    226.翻转二叉树题目链接:.-力扣(LeetCode)文章讲解:代码随想录视频讲解:听说一位巨佬面Google被拒了,因为没写出翻转二叉树|LeetCode:226.翻转二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦!快来打卡!本期视频的文字讲解版在「代码随想录」刷题网站:programmercarl.com......
  • 代码随想录算法训练营第十三天| 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子
    110.平衡二叉树题目链接:.-力扣(LeetCode)文章链接:代码随想录视频链接:后序遍历求高度,高度判断是否平衡|LeetCode:110.平衡二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦!快来打卡!本期视频的文字讲解版在「代码随想录」刷题网站:programmercarl.com,这里刷题顺序,详......
  • 代码随想录 -- 动态规划 -- 01背包理论基础
    46.携带研究材料(第六期模拟笔试)思路:dp[i][j]含义:在(0,i)之间任意选取物品放入容量为j的背包中,使背包的价值最大。递推公式:当前背包容纳不下第i个物品,不选第i个物品,此时背包的价值:dp[i][j]=dp[i-1][j]。当前背包容纳得下第i个物品时,且选择第i个物品,此时背包的价值:dp[i][j......
  • 代码随想录刷题学习日记
    仅为个人记录复盘学习历程,解题思路来自代码随想录代码随想录刷题笔记总结网址:代码随想录222.完全二叉树的节点个数给出一个完全二叉树,求出该树的节点个数。提供参数:根结点root主要操作:遍历所有节点,记录节点数。代码(递归法)大致如下:publicintcountNodes(TreeNoder......