# 动态规划
# 题目
# 1. 问题类： 路径问题
- 路径数量
- 最小路径
# 1. 路径数量
m x n 网格的左上角到右下角有多少条路径，要求只能向下或者向右？
# 状态定义：
定义f[i][j]为到达位置 (i,j) 的不同路径数量。
# 起始条件：
f[0][0]=1;
# 状态转移方程：
1. 当前位置只能 往下 移动，即有 f[i][j] = f[i-1][j]
2. 当前位置只能 往右 移动，即有 f[i][j] = f[i][j-1]
3. 当前位置即能 往下 也能 往右 移动，即有 f[i][j] = f[i][j-1] + f[i-1][j]
- 时间复杂度：O(n*m)
- 空间复杂度：O(n*m)
# 相关问题
- 输出全部路径？
- 某些位置不能通信？
影响中间状态值，即状态转移方程多出一个条件
当前位置是障碍物时，即有 f[i][j] = 0
- 有位置不能通行，判断是否可达？?
# 2. 问题类： 字符串组合问题
- 最长公共子串
- 最长公共子序列
- 交叉字符串
# 1.最长公共子串
输出两个字符串 s1 和 s2 的最长公共子串。
# 状态定义：
f[i][j]表示字符串s1 中第i个字符和s2中第j个字符为最后一个元素所构成的最长公共子串的长度
# 起始条件：
f[0][0]=0;
# 状态转移方程：
1. 当s1的第i个字符等于s2的第j个字符时，即有 f[i][j] = f[i-1][j-1]+1
2. 当s1的第i个字符不等于s2的第j个字符时，即有 f[i][j] = 0
f的维度为m+1，n+1，m，n分别为s1，s2的长度。
# 相关问题
- 求全部子序列
# 2.最长公共子序列
两个字符序列 s1 和 s2 的公共子序列中最长的序列。
不同于公共字串，公共子序列可以是不连续的，但是前后位置不变
# 状态定义：
f[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符组成的最长序列的长度
# 起始条件：
f[0][0]=0;
# 状态转移方程：
1. 当i为0，或者j为0是，f[i][j]=0
2. 当s1的第i个字符等于s2的第j个字符时，即有 f[i][j] = f[i-1][j-1]+1
3. 当s1的第i个字符不等于s2的第j个字符时，即有 f[i][j] = max（f[i-1][j]，f[i][j-1]）
f的维度为m+1，n+1，m，n分别为s1，s2的长度。
# 相关问题
- 求全部子序列
# 3.交叉字符串
字符串s1，s2能否组合成字符串s3
# 状态定义：
f[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符能否组成的s3的前i+j个字符
# 起始条件：
f[0][0]=0;
# 状态转移方程：
1. 当i为0，或者j为0是，f[i][j]=0
2. 当s1的第i个字符等于s3的第i+j-1 个字符时，即有 f[i][j] = f[i-1][j]
3. 当s2的第j个字符等于s3的第i+j-1 个字符时，即有 f[i][j] = f[i][j-1]
4. 当s1的第i个字符不等于s2的第j个字符时，即有 f[i][j] = false
f的维度为m+1，n+1，m，n分别为s1，s2的长度。
# 3. 问题类： 其他
# 1. 硬币组合
三种硬币，2元、5元、7元，每种硬币足够多，买一本书需要27元，用最少的硬币组合
# 建模
最终确定K枚硬币，且面值综合是27，则K-1枚硬币的面值和为27-ak，其中ak为第K枚硬币面值。
定义F(x)为面值为X的最少硬币数。
状态转移方程：
F(x) = min{F(x-2)+1,F(x-5)+1,F(x-7)+1}
初始条件： f(1) 无解 f(2)=1 无解 f(3) 无解
# 3. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。
# 建模
从i到j是一个回文串，那么从i+1到j-1一定也是一个回文串
我们定义f[i][j]表示字符串s的第i到j个字母组成的串是否为回文串
状态转移方程：
f(i,j) = f(i-1,j-1)
初始条件 长度小于3时，则i和j位置上值相同则是回文。
- 时间复杂度O(n^2)
- 空间复杂度O(n^2)
中心扩散法可能比动态规划更好
# 4 工作安排
We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.If you choose a job that ends at time X you will be able to start another job that starts at time X
# 建模
本题要求从给定的工作中找出最大的获利，我们定义dp(n)为从时间点n以后开始的工作中，可以获得的最大利益。那么对于一个开始结束时间为s,e，工资为p的工作job（s,e,p，它的状态转移方程可以表示为dp(s)=p+dp(e)。由于从s开始的工作可能存在多个，那么最终的状态转移方程就是dp(s)=max(pi+dp(ei))
#
public class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
// convert 3 arrays to one 2D array for sorting
int[][] jobs = new int[startTime.length][3];
for (int i = 0; i < startTime.length; i++) {
jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
}
// sort all jobs by startTime
Arrays.sort(jobs,Comparator.comparingInt(a -> a[0]));
// dp[i] stands for the max profit starts from jobs[i]
int[] dp = new int[jobs.length];
dp[jobs.length - 1] = jobs[jobs.length - 1][2];
// calculate from the end to start
// to make sure that the dp[next] of next job has been calculated
for (int cur = jobs.length - 2; cur >= 0; cur--) {
int next = findNext(cur, jobs);
dp[cur] = Math.max(
jobs[cur][2] + (next == -1 ? 0 : dp[next]),
dp[cur + 1]
);
}
return dp[0];
}
private int findNext(int cur, int[][] jobs) {
for (int next = cur + 1; next < jobs.length; next++) {
// the startTime of next job should be later than the endTime of current job
if (jobs[next][0] >= jobs[cur][1]) {
return next;
}
}
return -1;
}
}