红烧吹风机

分类

/ 注册

全部文章（共7篇）

题解 | #跳跃游戏(一)#

用dp[i]表示在第i个位置，能跳的最远距离。所以状态转移方程就是： dp[i] = max( dp[i-1],i+nums[i] ) 要么前一个位置跳的比当前位置远，要么现在这位置跳的远需要注意边界条件，当前位置最远能跳到的位置如果就是自己本身，那么就是无法跳到结尾的情况最终就是判断...

动态规划 C

2022-08-12

1 369

题解 | #兑换零钱(二)#

设dp[j]表示凑成j元一共有多少方法，dp[0] = 1，凑成0元只有一种方法，就是啥也不拿出来转移方程：dp[j] = dp[j] + dp[j-nums[i]] 这里的dp表是由二维的dp表压缩成一维的，还有一层用第i个硬币的含义。假设计算用第i个硬币凑成j元时候，等号左边是等待更新的状态，...

动态规划 C

2022-08-11

0 308

题解 | #兑换零钱(一)#

dp[j]表示兑换成j元最少需要多少张纸币，dp[0] = 0。 dp[j] = min( dp[j],dp[j-arr[i]] + 1 ) 转移方程表示兑换成j元要么用i-1张货币直接兑换成j元，要么i-1张货币兑换成j-arr[i]元，再加一张价值arr[i]的纸币。这里的转移方程是对原本二...

C 动态规划

2022-08-11

0 242

题解 | #最大正方形#

dp[i][j] 表示以（i,j）为右下角的正方形最长边长注意限制条件，当i=0 或者 j=0时候，边长最长就是1，其余情况根据（i-1,j）(i,j-1) (i-1,j-1)为右下角的正方形中最短边长决定 dp[i][i] = min( dp[i-1][j],dp[i][j-1],dp[i-1]...

动态规划 C

2022-08-11

0 262

题解 | #不同路径的数目(一)#

dp[i][j] 表示到达（i,j）有多少中方法。从最后一个状态出发，dp[i][j] = dp[i-1][j] + dp[i][j-1]，表示达到最后一个点的方法由走到(i-1,j)的方法和走到(i,j-1)的方法相加。注意限制条件，当i=0时，只能从当前点的上方下来，当j=0时，只能从...

C 动态规划

2022-08-11

0 292

题解 | #合法的括号字符串#

用dp[i][j] 表示以 i 开始， j结尾的字符串s[i][j]是否为合法的括号字符串确定dp[i][j]是否合法有两种方式，只要满足其中一个就合法 1、s[i]为左括号或者星号 s[j]为有括号或者星号,那么dp[i][j]完全依赖于的dp[i+1][j-1]的合法性 2、在[i,j]之间...

C 动态规划

2022-08-11

0 339

题解 | #三角形最小路径和#

使用动态规划，从最后一个状态进行分解，设 dp[i][j] 表示在坐标（i，j）处能得到的最小总和，因为下一个点只能是当前点下方一个点，或者右下方一个点，那么 dp[i][j] 的表达式就是 dp[i][j] = min（ dp[i-1][j],dp[i-1][j-1] ） + c[i][j]...

动态规划 C

2022-08-10

3 417