Word Break
题意
给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。 给出
s = “leetcode”,dict = [“leet”,”code”],返回 true 因为“leetcode”可以被空格切分成“leet code”。
思路
凡是和字符串有关的题,在应用动态规划方法时主要有两种思路:
- 用
dp[i][j]
表示子串s[i,j]
满足某一要求 - 用
dp[i]
表示子串s[0,i]
满足某一要求
记录Tamarous 的成长
给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。 给出
s = “leetcode”,dict = [“leet”,”code”],返回 true 因为“leetcode”可以被空格切分成“leet code”。
凡是和字符串有关的题,在应用动态规划方法时主要有两种思路:
dp[i][j]
表示子串s[i,j]
满足某一要求dp[i]
表示子串s[0,i]
满足某一要求有一个消息包含A-Z
通过以下规则编码:
1 2 3 4 5 |
'A' -> 1 'B' -> 2 ... 'Z' -> 26 |
现在给你一个加密过后的消息,问有几种解码的方式 ?如给出消息“12”,有两种解码的方法 AB(12) 或者 L(12),所以返回 2
。 继续阅读“LeetCode-91-Decode Ways”
在 Path Sum 和 Path Sum Ⅱ之后,Path Sum 大家庭又迎来了第三位成员。那么这个新成员又提出了什么样的要求呢?
题意是这样的:给出一棵二叉树和一个数值 sum,计算这棵树上的节点之和等于sum 的所有路径的条数。和之前不同的是,这道题中路径可以从树中的任何一个节点开始。 继续阅读“LeetCode-437-Path Sum Ⅲ”
题意:给出 n 组数,每组有两个数,第一个数总是比第二个数字小。如果两组数 (a,b) 和 (c,d) 之间,有 b < c,那么就称 (a,b)和 (c,d) 之间形成了一个chain。求出这 n 组数中能形成的最长的 chain 的长度。
例子:输入[[1,2], [2,3], [3,4]]
,因为[1,2] -> [3,4]
,所以返回2。 继续阅读“LeetCode-646-Maxinum Length of Pair Chain”
这个题也是一道动态规划题目。题意是:给出一系列数和一个目标数,使用+
和-
来使这些数字的和等于给定的目标数,求总共可行的方法数。
例子:输入[1, 1, 1, 1, 1]
,target = 3
,那么:
1 2 3 4 5 6 |
-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 |
所以最后的输出结果是:5 继续阅读“LeetCode-494-Target Sum”
这道题的题意是:给定一个数组形成的三角形,在从三角形的顶部出发的路径中,求节点数值相加结果为最小的和。
例子:输入
1 2 3 4 5 6 7 |
[ [2], [3,4], [6,5,7], [4,1,8,3] ] |
那么从顶部到底部最小的一条路径和为:2+3+5+1=11
。
思路:这是一道逆序的二维动态规划题,和之前看过的一道题–《龙与地下城》非常相似,都是逆序地从下往上求 DP数组。代码很简单,就不多做分析了,相信大家一看就能看懂。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { for (int i = triangle.size() - 2; i >= 0; i--) { for (int j = 0; j < i + 1; j++) { triangle[i][j] = min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j]; } } return triangle[0][0]; } }; |
又是一道非常典型的动态规划的题目。这道题的题意是:给定一个正整数n,那么总可以有若干个完全平方数之和等于n,求出最少的个数。如 n = 12, 12 = 4 + 4 + 4,因此返回3。又如 n = 13, 13 = 4 + 9,因此返回2。 继续阅读“LeetCode-279-Perfect Squares”
这道题是Unique Path的续集。
题意:输入一个二维数组,这个二维数组的元素如果是0,表示对应网格处没有障碍,可以正常向下或向右移动;如果这个数字是1,表示对应网格处有个障碍,机器人?将不能通过。 继续阅读“LeetCode-63-Unique Paths Ⅱ”
这道题是一道典型的动态规划问题。如图:
一个机器人的起始位置是左上方的网格,每次只能往下或者往右走。网格的长和高分别是 m 和 n,求机器人要走到图中的五角星处共有多少种走法? 继续阅读“LeetCode-62-Unique Paths”
链接在此。
解题思路:输入的 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])
。这即为本题的状态转移方程。根据该方程,我们不难写出下面的代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { size_t len = cost.size(); if (len == 1) { return cost[0]; } if (len == 2) { return cost[0] < cost[1] ? cost[0]:cost[1]; } // 表示跳到这个地方需要多少钱 vector<int> dp(len+1); dp[0] = 0; dp[1] = 0; dp[2] = min(dp[2-2] + cost[2-2], dp[2-1]+cost[2-1]); for(int i = 3; i <= len ;i++) { dp[i] = min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2]); } return dp[len]; } }; |