class Solution {
bool canJump(List<int> nums) {
var n = nums.length;
var maxJump = 0;
// 遍历每个位置，更新当前能到达的最大距离
for (var i = 0; i < n; i++) {
// 如果当前位置超出当前能到达的最大距离，说明无法到达当前位置
if (i > maxJump) {
return false;
}
// 更新当前能到达的最大距离
maxJump = max(maxJump, i + nums[i]);
}
return true;
}
}
class Solution {
int jump(List<int> nums) {
int n = nums.length;
int end = 0; // 当前能够到达的最远位置
int farthest = 0; // 经过最少步数能够到达的最远位置
int jumps = 0; // 跳跃次数
for (int i = 0; i < n - 1; i++) {
farthest = max(farthest, i + nums[i]); // 更新能够到达的最远位置
if (end == i) { // 需要跳一步
jumps++;
end = farthest; // 更新当前能够到达的最远位置
}
}
return jumps;
}
}
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回符合要求的最少分割次数。
class Solution {
int minCut(String s) {
var n = s.length;
// dp[i]表示字符串s[i..n-1]的最小分割次数
var dp = List<int>.filled(n, 0);
// isPalindrome[i][j]表示s[i..j]是否为回文字符串
var isPalindrome = List<List<bool>>.generate(n, (_) => List<bool>.filled(n, false));
// 初始化dp数组，最多需要分割n-1次
for (var i = 0; i < n; i++) {
dp[i] = n - i - 1;
}
// 从右向左遍历，计算dp和isPalindrome数组
for (var i = n - 1; i >= 0; i--) {
for (var j = i; j < n; j++) {
if (s[i] == s[j] && (j - i <= 1 || isPalindrome[i + 1][j - 1])) {
isPalindrome[i][j] = true;
// 如果s[i..j]是回文字符串，计算dp[i]的值
if (j == n - 1) {
dp[i] = 0;
} else {
dp[i] = dp[i].compareTo(dp[j + 1] + 1) > 0 ? dp[j + 1] + 1 : dp[i];
}
}
}
}
return dp[0];
}
}
注意点
判断回文字符串时，可以提前用动态规划算好，减少时间复杂度
给定一个无序的整数数组，找到其中最长上升子序列的长度。
class Solution {
int lengthOfLIS(List<int> nums) {
// 如果数组为空，则LIS长度为0
if (nums.isEmpty) {
return 0;
}
// 定义一个数组dp，dp[i]表示以第i个数字为结尾的LIS长度
var dp = List<int>.filled(nums.length, 1);
// 定义LIS的最大长度变量
var maxLength = 1;
// 遍历数组，计算dp[i]的值
for (var i = 1; i < nums.length; i++) {
// 遍历i之前的数字，找到所有小于nums[i]的数字，并计算dp[i]的值
for (var j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = dp[i].compareTo(dp[j] + 1) == 1 ? dp[i] : dp[j] + 1;
}
}
// 更新LIS的最大长度
maxLength = maxLength.compareTo(dp[i]) == 1 ? maxLength : dp[i];
}
return maxLength;
}
}
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
class Solution {
bool wordBreak(String s, List<String> wordDict) {
// 将单词列表转为 set 方便查找
var dict = wordDict.toSet();
// 定义一个数组用来记录 s 中前 i 个字符是否可以被单词拆分
var dp = List.filled(s.length + 1, false);
dp[0] = true; // 空字符串可以被任何单词拆分
// 遍历 s 的所有子串
for (var i = 1; i <= s.length; i++) {
for (var j = 0; j < i; j++) {
// 如果前 j 个字符可以被单词拆分，且 j 到 i 的子串在单词列表中出现过
// 那么前 i 个字符也可以被单词拆分
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break; // 如果已经可以被拆分了，就不用继续查找了
}
}
}
return dp[s.length];
}
}
