你是怎么想到的+复杂度
-
多重循环
- 定义DP数组，一般自顶向下，从起点到该位置的int，boolean
- 初始化DP数组
- 多重循环填充数组
568. Maximum Vacation Days
LeetCode wants to give one of its best employees the option to travel among N cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.
Rules and restrictions:
You can only travel among N cities, represented by indexes from 0 to N-1. Initially, you are in the city indexed 0 on Monday.
The cities are connected by flights. The flights are represented as a NN matrix (not necessary symmetrical), called flights representing the airline status from the city i to the city j. If there is no flight from the city i to the city j, flights[i][j] = 0; Otherwise, flights[i][j] = 1. Also, flights[i][i] = 0 for all i.
You totally have K weeks (each week has 7 days) to travel. You can only take flights at most once per day and can only take flights on each week's Monday morning. Since flight time is so short, we don't consider the impact of flight time.
For each city, you can only have restricted vacation days in different weeks, given an NK matrix called days representing this relationship. For the value of days[i][j], it represents the maximum days you could take vacation in the city i in the week j.
You're given the flights matrix and days matrix, and you need to output the maximum vacation days you could take during K weeks.
Example 1:
Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
Ans = 6 + 3 + 3 = 12.
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days
注意飞不到的时候如何处理，二维DP
public int maxVacationDays(int[][] flights, int[][] days) {
int N = flights.length;
int K = days[0].length;
int[][] dp = new int[N][K];
boolean[][] canReach = new boolean[N][K];
int res = 0;
// init : week1 start from city 0
for (int i = 0; i < N; i++) {
if (i == 0 || flights[0][i] == 1) {
dp[i][0] = days[i][0];
canReach[i][0] = true;
}
}
// dp
for (int j = 1; j < K; j++) {
for (int i = 0; i < N; i++) {
for (int k = 0; k < N; k++) {
// we can fly from city k to i
if ((k == i || flights[k][i] == 1) && canReach[k][j - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[k][j - 1] + days[i][j]);
canReach[i][j] = true;
}
}
}
}
for (int i = 0; i < N; i++) {
res = Math.max(res, dp[i][K - 1]);
}
return res;
}
688. Knight Probability in Chessboard
给一个N*N的棋盘，走的步数K，开始位置x，y，求K步之后骑士仍在棋盘里的概率。
棋盘上的动态规划，三维的动态规划 k，x，y，dp数组表示，K步之后骑士有几种走法能停在x，y点。最后加起来除以8的k次方得到概率。递推公式是dp[k][i][j] += dp[k-1][x][y]，从x，ymove到i，j。
K从0开始想就能想通了。k如果等于0，在原地不动，概率100%，k如果等于1，有八种走法，算出有几种能停在棋盘里。K等于2时。。。
public double knightProbability(int N, int K, int r, int c) {
int[] directionX = {1, 2, -1, -2, 1, 2, -1, -2};
int[] directionY = {2, 1, -2, -1, -2, -1, 2, 1};
// dp[k][i][j] = sum(dp[k-1][i][j])
double[][] dp = new double[N][N];
// initialize all 0
dp[r][c] = 1;
for (int k = 1; k <= K; k++) {
double[][] temp_dp = new double[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// i, j can be reached by 8 positions on the board
for (int p = 0; p < 8; p++) {
if (i + directionX[p] >= 0 && i + directionX[p] < N
&& j + directionY[p] >= 0 && j + directionY[p] < N) {
temp_dp[i][j] += dp[i + directionX[p]][j + directionY[p]];
}
}
}
}
dp = temp_dp;
}
double total = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
total += dp[i][j];
}
}
return total / Math.pow(8, K);
}
-
DFS + Memory Search
44，72很像，递归的定义和与前一步的关系（三种情况分类讨论取最值）
44. Wildcard Matching
isMatch("ab", "?*") → true
isMatch("aab", "c * a * b") → false
?代表单个任意字符， * 代表空或单个或多个任意字符，与前一个字符无关
public boolean isMatch(String s, String p) {
二维DP， i表示s的0-i子串，j同理，dp[i][j]表示这两个子串是否匹配。
自顶向下的DP，根据DP数组的定义可知。
初始化难想的是如果p以一个或多个开头，那么需要把他们都标记为true（默认false）
递推公式：
如果p扫到一个字符或者“ ？”，处理比较简单。
如果扫到“ * “是难点所在因为情况比较复杂，跟518很像，每种情况单独讨论，有任何一种成立，那么就是true。
1 如果把 * 当空，那么比p.substring(0, j-1)和s.substring(0,i)。
2 把 * 当一个或多个任意字符，考虑caba, c
c和c* 匹配，。。。，cab和c匹配，那么caba就和c匹配，所以知道dp[i][j] = dp[i-1][j]
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][ n + 1];
// 1 initialize
dp[0][0] = true;
// "**ho"
for (int j = 1; j < n + 1; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = true;
} else {
break;
}
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (p.charAt(j - 1) != '*') {
// 最后一个字符相等，且前面的是匹配的
dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') && dp[i - 1][j - 1];
} else {
// 把 * 当成空处理 || 当成 一个或多个任意字符处理
// 1. 匹配0个字符：dp[i][j] = dp[i][j-1]
// 2. 匹配1个字符：dp[i][j] = dp[i-1][j-1]
// 3. 匹配多个字符：dp[i][j] = dp[i-1][j]
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
}
return dp[m][n];
}
72. Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
https://leetcode.com/problems/edit-distance/discuss/25911
add和delete对称，replace是各退一步
注意注释里提的，Math.min只能比两个
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// dp[i][j] -> substring(0, i) substring(0, j)
// initialize
for (int i = 0; i <= n; i++) {
dp[0][i] = i;
}
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// min 只能比两个
// add (append) 对称情况 or delete i or replace i by j
dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[m][n];
}
714. Best Time to Buy and Sell Stock with Transaction Fee
198. House Robber
这两道题比较像，基础的DP，都是有两种状态
第i 天买的话最高利润，第i天卖的话最高利润，do nothing已经包含在两个dp数组中了。https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108871
第i个屋子偷的话最多挣多少钱，第i个屋子不偷的话最多挣多少钱
都是用两个一维数组记录。(都有follow-up，有时间做一下）
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] steal = new int[nums.length + 1];
int[] notSteal = new int[nums.length + 1];
// initialize 0, 0
for (int i = 1; i <= nums.length; i++) {
steal[i] = nums[i - 1] + notSteal[i - 1];
notSteal[i] = Math.max(notSteal[i - 1], steal[i - 1]);
}
return Math.max(steal[nums.length], notSteal[nums.length]);
}
public long houseRobber(int[] A) {
// write your code here
int n = A.length;
if(n == 0)
return 0;
long []res = new long[n+1];
res[0] = 0;
res[1] = A[0];
for(int i = 2; i <= n; i++) {
res[i] = Math.max(res[i-1], res[i-2] + A[i-1]);
}
return res[n];
}
public int maxProfit(int[] prices, int fee) {
// pay fee when buying
int days = prices.length;
int[] buy = new int[days]; // we buy at day i
int[] sell = new int[days]; // we sell at day i
buy[0] = -prices[0] - fee; // sell[0] = 0
for (int i = 1; i < days; i++) {
// buy or not
buy[i] = Math.max(sell[i - 1] - prices[i] - fee, buy[i - 1]);
// sell or not
sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);
}
return sell[days - 1];
}
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
矩阵上的DP
516. Longest Palindromic Subsequence 补DP做法
subsequence和substring不一样 比如 bbbab 最长的sub sequency是bbbb，所以返回4
memo search比较好理解，helper函数传入头尾指针，如果头尾的字符相同，那么该字符串的最长回文长度就是2+中间部分的最长回文长度，进行递归。如果头尾的字符不同，那么头指针+1尾指针不动，或尾-1头不动。查过的substring用memo记录。helper函数传入头尾指针和memo二维数组。memo[i][j]表示以i, j分割出的substring的最长回文长度
Palindromic常用套路dp[i][j]，指定起点终点，往中间找
Palindromic还有一种方法叫做extend，定义中心pivot然后向两边扩展，pivot可以是a，也可以是aa这种
class Solution {
public int longestPalindromeSubseq(String s) {
if (s == null || s.length() == 0) {
return 0;
}
return helper(s, 0, s.length() - 1, new Integer[s.length()][s.length()]);
}
public int helper(String s, int start, int end, Integer[][] memo) {
if (memo[start][end] != null) {
return memo[start][end];
}
if (start > end) {
return 0;
}
if (start == end) {
return 1;
}
if (s.charAt(start) == s.charAt(end)) {
memo[start][end] = 2 + helper(s, start + 1, end - 1, memo);
} else {
memo[start][end] = Math.max(helper(s, start + 1, end, memo), helper(s, start, end - 1, memo));
}
return memo[start][end];
}
}
673. Number of Longest Increasing Subsequence
Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
找到最长递增子序列的个数
思路来自于找最长连续递增子序列的长度，一个DP数组记录截止到当前位置最长的递增子序列长度，另一个DP数组记录到当前位置的子序列，有几种可能构造出最长长度。何时更新第二个DP数组是复杂的地方。
DP写法需要学习
- DP数组在哪初始化
- 全局变量在何处更新
class Solution {
public int findNumberOfLIS(int[] nums) {
int N = nums.length;
if (N <= 1) return N;
int[] lengths = new int[N]; //lengths[i] = length of longest ending in nums[i]
int[] counts = new int[N]; //count[i] = number of longest ending in nums[i]
Arrays.fill(counts, 1);
for (int j = 0; j < N; ++j) {
for (int i = 0; i < j; ++i) if (nums[i] < nums[j]) {
if (lengths[i] >= lengths[j]) {
lengths[j] = lengths[i] + 1;
counts[j] = counts[i];
} else if (lengths[i] + 1 == lengths[j]) {
counts[j] += counts[i];
}
}
}
int longest = 0, ans = 0;
for (int length: lengths) {
longest = Math.max(longest, length);
}
for (int i = 0; i < N; ++i) {
if (lengths[i] == longest) {
ans += counts[i];
}
}
return ans;
}
}
329. Longest Increasing Path in a Matrix
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].
DP做不了的原因
网友评论