LeetCode上几道和字符串有关的动态规划问题

Word Break

题意

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。 给出

s = “leetcode”,dict = [“leet”,”code”],返回 true 因为“leetcode”可以被空格切分成“leet code”

思路

凡是和字符串有关的题,在应用动态规划方法时主要有两种思路:

  • dp[i][j]表示子串s[i,j]满足某一要求
  • dp[i]表示子串s[0,i]满足某一要求

继续阅读“LeetCode上几道和字符串有关的动态规划问题”

LeetCode-494-Target Sum

这个题也是一道动态规划题目。题意是:给出一系列数和一个目标数,使用+-来使这些数字的和等于给定的目标数,求总共可行的方法数。

例子:输入[1, 1, 1, 1, 1]target = 3,那么:

所以最后的输出结果是:5 继续阅读“LeetCode-494-Target Sum”

LeetCode-120-Triangle

这道题的题意是:给定一个数组形成的三角形,在从三角形的顶部出发的路径中,求节点数值相加结果为最小的和。

例子:输入

那么从顶部到底部最小的一条路径和为:2+3+5+1=11

思路:这是一道逆序的二维动态规划题,和之前看过的一道题–《龙与地下城》非常相似,都是逆序地从下往上求 DP数组。代码很简单,就不多做分析了,相信大家一看就能看懂。

代码如下:

LeetCode-746-Min Cost Climbing Stairs

链接在此。

解题思路:输入的 cost 向量的长度 len即为台阶的级数。我们可以生成一个长度为len+1的向量 dp,dp[i]表示跳到第 i 个位置(从0开始计数)需要的费用。例如 dp[0]表示跳到第0个位置的cost,为0;dp[1]表示跳到第1个位置的 cost,因为起始 index 可以为1,所以 dp[1] = 0;dp[2]表示跳到第2个位置的 cost,因为一次可以跳一步或者两步,因此 dp[2]的值有两种可能:

* 从第0个位置跳过来,所以 dp[2] = dp[0] + cost[0];
* 从第1个位置跳过来,所以 dp[2] = dp[1] + cost[1];
因此我们应该取这两种情况中较小的那一个:dp[2] = min(dp[2-2] + cost[2-2], dp[2-1]+cost[2-1]);

下面我们来推导状态转移方程:
dp[i]表示跳到第 i 个位置,它的值有两种可能:
* 从第 i-2 个位置跳过来,因此dp[i] = dp[i-2]+cost[i-2]
* 从第 i-1 个位置跳过来,因此dp[i] = dp[i-1]+cost[i-1]

因此,dp[i] = min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2])。这即为本题的状态转移方程。根据该方程,我们不难写出下面的代码: