序列型动态规划（动态规划的入门）
想问题四步走：
state: f[i]表示“前i”个位置/数字/字母,(以第i个为)...
function: f[i] = f[j] ... j 是i之前的一个位置
intialize: f[0]..
answer: f[n-1]..
计算方案总数的问题，初始化一定要初始化为1.
切割型动规
如果限制了切割的子字符串的个数（k），那么就是二位DP
f[i][j] 前i个字符，切成j个单词是否可行。
如果没有限制, 一维DP f[i]
两个序列的DP
二维
f[i][j] 表示第一个字符串的前i个字符配上第二个字符串的前j个字符
研究第i个字符和第j个字符的匹配关系
Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example: A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
Idea
State: f[i] 是否能从起点跳到第i个位置
Function:
f[i] = OR(f[j], j < i && A[j] + j >= i)
Init:
f[0] = true
Answer:
f[n - 1]
Code
public class Solution {
public boolean canJump(int[] nums) {
boolean[] dp = new boolean[nums.length];
dp[0] = true;
for(int i = 1; i < nums.length; i++) {
for(int j = 0; j < i; j++) {
if(dp[j] && nums[j] + j >= i) {
dp[i] = true;
break;
}
}
}
return dp[nums.length - 1];
}
}
Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example: Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note: You can assume that you can always reach the last index.
Code
public class Solution {
public int jump(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
// state
int[] f = new int[n];
// function
for(int i = 1; i < n; i++) {
// init
f[i] = Integer.MAX_VALUE;
for(int j = 0; j < i; j++) {
// MAX_VALUE 说明无法跳到当前位置
if(f[j] != Integer.MAX_VALUE && nums[j] + j >= i) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
// answer
return f[n - 1];
}
}
Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
分析
function:
f[i] = f[i - 1] + f[i - 2]
Init:
f[0] = 1
计算方案总数的问题，初始化一定要初始化为1.
code
滚动数组优化
public class Solution {
public int climbStairs(int n) {
if(n < 2) {
return 1;
}
int[] dp = new int[2];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i % 2] = dp[(i - 1) % 2] + dp[(i - 2) % 2];
}
return dp[n % 2];
}
}
Longest Common Subsequence
Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.
Example For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.
For "ABCD" and "EACB", the LCS is "AC", return 2.
Idea
f[i][j] 表示前i个字符配上前j个字符的LCS的长度
function:
s1[i] != s2[j] : f[i][j] = max(f[i - 1][j], f[i][j - 1])
s1[i] == s2[j] : f[i][j] = max(f[i - 1][j], f[i][j - 1], f[i - 1][i - 1] + 1)
Init: 第0行，第0列为0
Answer:
f[n1][n2]
Code
public int longestCommonSubsequence(String A, String B) {
// write your code here
int n = A.length();
int m = B.length();
int[][] f = new int[n + 1][m + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
// f[i - 1][j] 不要第i个，要第j个
// f[i][j - 1] 要第i个，不要第j个
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
if(A.charAt(i - 1) == B.charAt(j - 1)) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
return f[n][m];
}
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
Analyze
为什么想到用DP： 两个字符串，求最小什么什么，而且是序列不是集合
State:
f[i][j] 前i个字符变成前j个字符，最小需要多少步
Function:
就看最后一个字符，如何让他们相等
相等怎么做：f[i][j] = min(f[i - 1][j]删除, f[i][j - 1]增加,f[i - 1][j - 1])
不相等怎么办：f[i][j] = min(f[i - 1][j]删除, f[i][j - 1]增加,f[i - 1][j - 1] + 1 替换)
Init：
f[i][0] = i
f[0][j] = j
Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example: S = "rabbbit", T = "rabbit"
Return 3.
2. S = "ABCABC", T = "ABC"
Return 4.
Analyze
首先两个字符串，求多少种方案，而且是sequence，可以尝试用动态规划
State:
f[i][j] 从S的前i个字符取出T的前j个字符，有多少种方案。
Function: 现在的状态和之前的哪些状态有关，只是和当前字符有关，可以从前一个字符跳过来
S[i] == T[j]
S的第i个字符要不要
不要：`f[i - 1][j]`
要：`f[i - 1][j - 1]`
Init:
f[i][0] = 1 挑出一个空串
f[0][i] = 0 空串挑不出来
Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab", Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
Idea
State: 直接套 f[i] 前i个字符，最少切几刀，能成回文分割
Function: 最后一刀切在哪儿
f[i] = min{f[j] + 1}, j < i && j + 1 ~ i 是回文
Init: 初始值最大,最多可以切几刀 f[i] = i - 1 (f[0] = -1)
如何理解前0个字符？ 其实就是空串自己 f[0] = -1 如何理解？f[0] + 1 = 0 不切 比如"aba" 字符串的动归题一般要把第0位给空出来
Answer: f[n]
Code
public class Solution {
public int minCut(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int n = s.length();
// 区间动归
boolean[][] isPanlindrome = isValid(s);
//state
int[] f = new int[n + 1];
// init
for(int i = 0; i < f.length; i++) {
f[i] = i - 1;
}
// function
for(int i = 1; i <= n; i++) {
for(int j = 0; j < i; j++) {
if(isPanlindrome[j][i - 1]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
return f[n];
}
public boolean[][] isValid(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
// init
for(int i = 0; i < n; i++) {
dp[i][i] = true;
}
for(int i = 0; i < n - 1; i++) {
if(s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
}
}
// 枚举长度，一个大区间依赖于小区间
for(int l = 2; l < n; l++) {
for(int i = 0; i + l < n; i++) {
if(dp[i + 1][i + l - 1] && s.charAt(i) == s.charAt(i + l)) {
dp[i][i + l] = true;
}
}
}
return dp;
}
}