夜渡寒鸦呀
夜渡寒鸦呀
全部文章
分类
题解(57)
归档
标签
去牛客网
登录
/
注册
夜渡寒鸦呀的博客
全部文章
(共8篇)
题解 | #剪绳子#
C语言求解 剪绳子 解题思路 动态规划问题,假如一段绳子为n=10米,那么将这段绳子看成两部分,可能的切割位置在 1~9这9个位置之间,因此求一个最大值,dp[10]=max(1*dp[9],2*dp[8],3*dp[7]......9*dp[1]),因此正向计算,dp[1]=1,dp[2]=2,d...
C
动态规划
2022-06-08
0
435
题解 | #礼物的最大价值#
C语言解礼物的最大值 解题思路:一个经典的动态规划问题,求方格路径的最大值,例如求dp[i][j],表示位置i,j的最大值,由于路径只能向右或者向下,也就是i,j位置只能来源于(i-1,j)或者是(i,j-1),求其最大值即可。dp[i][j]=max(dp[i-1][j],dp[i][j-1])...
C
动态规划
2022-05-20
0
454
题解 | #把数字翻译成字符串#
C语言 把数字翻译成字符串 1. 解题思路 动态规划问题,对于一串字符 1223424220238012,不妨设求第n个字符的可能情况。那么首先需要考虑的是这个字符nums[n],有两种大的情况,1.能否和前一个字符组成10~26之间的数,自身能否独立成一个新的数。 case1: 自身为0,只能依附...
C
动态规划
2022-05-18
0
456
题解 | #跳台阶扩展问题#
C语言青蛙跳台阶扩展 思路: 考虑跳n级台阶,可以从(n-1)跳一层、(n-2)跳两层、(n-3)跳3层、、、(n-n)跳n层上来,所以dp[n]=dp[n-1]+dp[n-2]+...+dp[0] 同样的 dp[n+1]=dp[n]+dp[n-1]+dp[n-2]+...+dp[0] = 2*d...
C
动态规划
2022-05-18
0
335
题解 | #斐波那契数列#
C语言斐波那契数列 解题思路:和上一题的青蛙跳台阶一样 使用动态规划解决,但是时间复杂度是O(n),要是想将时间复杂度降到O(logn),emmmmm * * @param n int整型 * @return int整型 * * C语言声明定义全局变量请加上static,防止重复定...
C
动态规划
2022-05-18
0
336
题解 | #跳台阶#
C语言求解青蛙跳台阶问题 解题思路:很基本的动态规划问题。假设青蛙求跳n级台阶,那么青蛙的上一级台阶只能是(n-1)级台阶,或者是(n-2)级台阶,所有dp[n]=dp[n-1]+dp[n-2] 使用两个变量保存一下两个前驱dp即可。 * * @param number int整型 *...
C
动态规划
2022-05-18
0
345
题解 | #连续子数组的最大和(二)#
C语言求解连续子数组的最大和(二) 解题思路: 由于已经使用动态规划解决了连续子数组的最大和(一),那么思路相同,只不过这次的输出是要求输出这个连续子数组,那么可以添加一个变量,用于记录返回数组的末尾元素位置,同时还需要一个变量记录一下连续的数组长度。 遇到的坑: 2.1 由于遇到多个最优解...
C
动态规划
2022-05-17
2
524
题解 | #连续子数组的最大和#
C语言求解连续子数组的最大和 解题思路:动态规划(dp)问题,对于一个连续的数组:1 -2 3 10 -4 7 2 -5,当计算第i个dp时,此时需要根据dp[i-1]来推算出dp[i]的值,此时dp[i]相比于dp[i-1]的变数 只有a[i]这个值,接下来应该判断a[i]是否有可能添加到dp...
C
动态规划
2022-05-17
0
552