首页 > 其他分享 >[代码随想录]Day34-动态规划part02

[代码随想录]Day34-动态规划part02

时间:2023-09-02 19:22:27浏览次数:49  
标签:obstacleGrid lcol int Day34 part02 随想录 ++ lrow dp

题目:62. 不同路径

思路:

首先想到的是数论方法组合数其实就是向右和向下的步数是固定的,就找一个组合的个数就可以了。

状态转移方程:一个位置的路径数就是,上面位置和左面位置路径数的和

按照动规五部曲来分析:

  1. 确定dp数组(dp table)以及下标的含义:

    dp[i][j]:表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。

  2. 确定递推公式:

    想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。此时在回顾一下 dp[i - 1][j] 表示啥,是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。那么很自然,dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来。

  3. dp数组的初始化:

    如何初始化呢,首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。

    所以初始化代码为:

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
  1. 确定遍历顺序:

    这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。这样就可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。

  2. 举例推导dp数组:

image.png

代码:

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp{
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
		dp[0][j] = 1
	}
    for i := 1; i < m; i++ { // 其实就是一个杨辉三角
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

参考:

代码随想录

题目:63. 不同路径 II

思路:

和上面差不多,多了一个检查的操作。

代码:

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	lrow, lcol := len(obstacleGrid), len(obstacleGrid[0])
	//如果在起点或终点出现了障碍,直接返回0
	if obstacleGrid[lrow-1][lcol-1] == 1 || obstacleGrid[0][0] == 1 {
		return 0
	}
	// 定义一个dp数组
	dp := make([][]int, lrow)
	for i, _ := range dp {
		dp[i] = make([]int, lcol)
	}
	// 初始化, 如果是障碍物, 后面的就都是0, 不用循环了
	for i := 0; i < lrow && obstacleGrid[i][0] == 0; i++ {
		dp[i][0] = 1
	}
	for i := 0; i < lcol && obstacleGrid[0][i] == 0; i++ {
		dp[0][i] = 1
	}
	// dp数组推导过程
	for i := 1; i < lrow; i++ {
		for j := 1; j < lcol; j++ {
			// 如果obstacleGrid[i][j]这个点是障碍物, 那么dp[i][j]保持为0
			if obstacleGrid[i][j] != 1 {
				// 否则我们需要计算当前点可以到达的路径数
				dp[i][j] = dp[i-1][j] + dp[i][j-1]
			}
		}
	}
	return dp[lrow-1][lcol-1]
}

参考:

代码随想录

标签:obstacleGrid,lcol,int,Day34,part02,随想录,++,lrow,dp
From: https://www.cnblogs.com/wtcsky/p/17674091.html

相关文章

  • 代码随想录——数组篇
    二分查找题目链接注意:求均值防溢出,left+(right-left)/2等价于(left+right)/2。原地移除元素题目链接给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用O(1)额外空间并原地修改输入......
  • [代码随想录]Day33-动态规划part01
    题目:509.斐波那契数思路:动规五部曲:这里我们要用一个一维dp数组来保存递归的结果确定dp数组以及下标的含义dp[i]的定义为:第i个数的斐波那契数值是dp[i]确定递推公式为什么这是一道非常简单的入门题目呢?因为题目已经把递推公式直接给我们了:状态转移方程dp[i]=dp[i-......
  • [6]-代码随想录算法训练营-dat7-哈希表-part2
    代码随想录算法训练营第七天|哈希表-part21.LeetCode454.四数相加II题目https://leetcode.cn/problems/4sum-ii/submissions/思路无刷随想录后想法将四数相加转化为两数之和借用unordered_map,利用两数之和思想解决本问题实现困难代码尚模糊,不过整个......
  • [代码随想录]Day30-贪心算法part04
    题目:860.柠檬水找零思路:收到钱三种情况:5刀:直接收起来就可以了,不需要找钱10刀:收到10刀,需要找5刀,如果没有5刀,就返回false,否则5刀-120刀:收到20刀(但是没用,找钱也不能找20所以不需要记录数量),优先考虑找105,因为10只能在这里用,其次再考虑找555代码:funclemonadeChange(bil......
  • 代码随想录第6天|242.有效的字母异位词;349.两个数组的交集;202.快乐数;1.两数之和;
     unordered_map<int,int>map;  unordered_set<int>result;vector<vector<int>>res(n,vector<int>(n,0));声明了长度为n*n的二维数组在C++中,auto是一个关键字,用于实现类型推导,使编译器能够根据变量的初始化表达式来自动推断其数据类型。它在C++11标准中引入,......
  • [代码随想录]Day29-贪心算法part03
    题目:1005.K次取反后最大化的数组和思路:思路是:先把负数从小到大变成正数(即绝对值由大到小)如果还需要变化(k>0),就变化最小的数在第一步变化的同时顺便记录一个数组和,那么结束之后会有三种情况:k==0;也就是说负数的个数大于等于k,直接返回结果k%2==0;此时全是正整数,......
  • Day34(2023.08.22)
    行程8:45    到达上海市信息安全测评认证中心(黄浦区陆家浜路1308号)9:00  久事体育软件测试11:30--13:00   吃饭休息13:00  久事体育软件测试17:00      下班......
  • 代码随想录第4天|链表复习
    做这种算法题真的要放平心态,你想不到思路的时候不要觉得自己太笨,其实想不到很正常,今天环形链表和相交链表这两道题,真的一点思路都没有,环形链表是最难理解的,在课堂上学的链表上的那点东西拿来做这种题确实还是差很多,我真的非常感谢这个做题的训练营,没有它我自己真的做不下去,现在跟......
  • 代码随想录算法训练营第二十四天| 理论基础 77. 组合
     理论基础    卡哥建议:其实在讲解二叉树的时候,就给大家介绍过回溯,这次正式开启回溯算法,大家可以先看视频,对回溯算法有一个整体的了解。   题目链接/文章讲解:https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8......
  • 代码随想录算法训练营第二十三天| 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜
     669. 修剪二叉搜索树    卡哥建议:这道题目比较难,比 添加增加和删除节点难的多,建议先看视频理解。   题目链接/文章讲解:https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html   视频讲解:https://www.......