动态规划 && 贪婪算法
1· 剪绳子（14 剑指offer ）
- 需要先从 base case 开始寻找规律 ，绳子长度为 n(2 <=n<=58)， 剪成m 段（2 <= m）, 所以说
以下是动态规划的解法： n = 1,2,3,4 是 base case
转移方程式： res[i] = math.max(res[j] + res[ i - j] ) -> j from 1 to i / 2;
public static int maxProduceAfterCutting(int length) {
if(length == 2)
return 1;
if(length == 3)
return 2;
if(length == 4)
return 4;
int [] res = new int[length + 1];
res[0] = 1;
res[1] = 1;
res[2] = 2;
res [3] = 3;
int max = 1;
for(int i = 4; i<=length; i++){
for(int j = 1; j <= i/2; j++){
int tmp = res[j] * res[ i - j];
if(tmp > res[i])
res[i] = tmp ;
}
}
return res[length];
}
- 以下是贪婪算法 的做法, 但是有3个数学的基本证明必须记住
- 假设 ni >= 5 , 3 * ( ni - 3) > ni ? => 2ni > 9 ? 所以说 当 ni >= 5时，把3 切出来 可以乘机最大化
- 当 ni = 4 时， 2* 2 > 3 * 1 , 当 ni = 4 时，把2 切出来，可以乘机最大化
- 当 2 * 2* 2 < 3 * 3， 当既可以切 2个以上的3 ，又可以切2个以上的 2 时，把3 切出来 可以乘机最大化
public static int maxProduceAfterCutting(int length) {
if(length == 2)
return 1;
if(length == 3)
return 2;
if(length == 4)
return 2;
int timesOf3 = length/3;
/* 说明可以划出一个 4 */
if(length - timesOf3 * 3 == 1){
timesOf3 = timesOf3 -1 ;
}
int timesOf2 = (length - 3 * timesOf3) /2;
return (int) Math.pow(3, timesOf3) * (int)Math.pow(2, timesOf2);
}
2· 匹配2个字符串的模式（19 剑指offer ）
- match pattern 的题型
/*
状态表示： f[i][j] 表示 s[i, ...] 和 p[j, ...] 相匹配
状态转移：
1. p[j] 是正常字符， f[ i ][ j ] = s[i] = p[j] && f[i+1][j+1]
2. p[j] 是‘ . ’, f[ i ][ j ] = f[ i+1][ j+1]
3. p[ j + 1 ] 是 ‘ * ’ ， f[ i ][ j ] = f[ i ][ j+2] || f [i+1][ j ]
*/
class Solution {
int n,m;
int[][] f ;
public boolean isMatch(String s, String p) {
n = s.size();
m = p.size();
f = new int[n+1][m+1];
for(int i=0; i<n+1; i++)
for( int j =0; j< m+1; j++)
f[i][j] = -1;
return dp(0,0,s,p);
}
public dp(int x, int y, String s, String p) {
if(f[x][y] != null) return f[x][y];
if( y == m )
return f [x][y] = x == n;
}
}
3.Two City Scheduling（1029.leetcode）
- 方一 ：用到了 PriorityQueue 的数据结构
public int twoCitySchedCost(int[][] costs) {
int countA = 0;
int countB = 0;
int res = 0;
for( int[] city : costs){
int diff = Math.abs(city[0], city[1]);
if(city[0] < city[1]){
res += city[0];
countA ++;
pqA.offer(city[0]);
} else {
res += city[1];
countB ++;
pqB.offer(city[ 1])
}
} // for
while( countA > countB) {
res += pqA.poll();
countA --;
countB++;
}
while( countA < countB ){
res += pqB.poll();
countB --;
countA++;
}
return res;
}
- 方二 ：用到了 DP 的思想
4. Uncrossed Lines（1035.leetcode）
- dp 思想
public int maxUncrossedLines(int[] A, int[] B) {
int m = A.length , n = B.length , dp[][] = new int[m + 1][ n + 1];
for(int i = 11; i<= m ; i++){
for( int j = 1; j<= n; j++){
if( A[i - 1][j - 1] == B[i - 1][j - 1])
dp[i][j] = 1 + dp[i -1 ][j - 1];
else
dp = Math.max( dp[i - 1][ j], dp[ i ][j - 1]);
}
}
return dp[m][n];
}
5.Paint House（ 256. leetcode）
- easy 类型
- 转移方程式：
- paintCurrentRed = min(paintpreviousGreen , paintPreviousBlue) + costs[ i + 1][ 0 ];
public int minCost(int[][] costs){
if(cost == null || cost.length ==0) return 0;
int lastR = costs[0][0];
int lastG = costs[0][1];
int lastB = costs[0][2];
for(int i = 1; i < costs.length ; i++){
int curR = Math.min(lastG, lastB) + costs[i][0];
int curG = Math.min(lasrR, lastB) + costs[i][1];
int curB = Math.min(lastR, lastG) + costs[i][2];
lastR = curR;
lastG = curG;
lastB = curB;
}
return Math.min(lastR, lastG< lastB ? lastG : lastB);
}
6. House Robber（198. leetcode）
- step 1. find recursion relation
- rob(i) = Math.max( rob( i -2 )+ currentHouseV , rob( i -1));
- step 2. recursive( top - down)
converting the recurrent relation form step1 , 这个算法 重复跑 同样的 i 值 多次， 需要改进
public int rob( int[ ] nums){
return rob( nums, nums.length - 1);
}
private int rob( int[ ] nums, int i){
if( i < 0) return 0;
return Math.max( rob( nums, i -2 ) + nums[i] , rob( nums, i -1 ) );
}
- Step 3. Recursive + memo (top-down). 这里使用一个 array memo 来记录 i 值， runO(n) time. Space complexity O(n)
int [] memo ;
public int rob( int [] nums){
memo = new int[ nums.length + 1];
Arrays.fill(memo , -1);
return rob( nums, nums.length -1 );
}
private int rob( int[] nums, int i){
if(i < 0) return 0;
if( memo[i] >= 0) return memo[i];
int result = Math.max( rob( i -2) + nums[ i] , rob(i -1));
memo[i] = result;
return result;
}
- Step 4. Iterative + memo (bottom-up)
用for loop 而不用 recurrsion call
public int rob(int[] nums){
if (nums.length == 0) reutrn 0;
int[ ] memo = new int[ nums.length + 1];
memo[0] = 0;
memo[1] = nums[0];
for(int i= 1; i < nums.length ; i ++){
int value = nums[i];
memo[ i+ 1] = Math.max( memo[i] , memo[ i -1]+ value );
}
return memo[nums.length];
}
- Step 5. Iterative + 2 variables (bottom-up)
因为前面只用了 memo[ i] and memo[ i -1] , so going just 2 steps back. We can hold them in 2 variables instead. This optimization is met in Fibonacci sequence creation and some other problems [to paste links]
/* the order is : prev2 , prev2 , num*/
public int rob(int[] nums){
if(nums == null || nums.length == 0) return 0;
int prev1 = 0;
int prev2 = 0;
for(int num : nums){
int tmp = prev1;
}
}
7.Paint Fence（ 276.leetcode）
https://www.youtube.com/watch?time_continue=3&v=deh7UpSRaEY
网友评论