數(shù)字三角形模型
摘花生（線性DP）
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = 110;
static int[][] dp = new int[N][N];
static int[][] a = new int[N][N];
static int t = 0;
static int r = 0, c = 0;
public static void main(String[] args) throws Exception{
t = Integer.parseInt(br.readLine());
while(t-- > 0) {
String[] rc = br.readLine().split(" ");
r = Integer.parseInt(rc[0]);
c = Integer.parseInt(rc[1]);
for(int i = 1; i <= r; i++) {
String[] aa = br.readLine().split(" ");
for(int j = 1; j <= c; j++) {
a[i][j] = Integer.parseInt(aa[j - 1]);
}
}
for(int i = 1; i <= r; i++) {
for(int j = 1; j <= c; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
}
}
System.out.println(dp[r][c]);
}
}
}
最低通行費(fèi)（線性DP+曼哈頓距離 / 記憶化搜索）???
法一：線性DP
這題目最重要的是根據(jù)必須在（2N-1）個(gè)單位時(shí)間內(nèi)穿越出去，推導(dǎo)出此題的解題的重要性質(zhì)。
曼哈頓距離：
兩個(gè)點(diǎn)在標(biāo)準(zhǔn)坐標(biāo)系上的絕對(duì)軸距總和，d=|x2?x1|+|y2?y1
此題雖然說可以向上下左右四個(gè)方向移動(dòng)，但是根據(jù)2n-1個(gè)單位時(shí)間的限制結(jié)合曼哈頓距離，我們可以得到：
（1，1）->（n,n）的曼哈頓距離為2n-2,但是題目要求在2n-1的單位時(shí)間穿越出去，所以我們每次走一步必須可以使曼哈頓距離縮短1，否則是無用的，因此我們得到我們只能向下或向右走，這樣才能每走一步就距離終點(diǎn)更近。這樣的話就和最經(jīng)典的上一題??基本差不多啦~
public class Main{
static Scanner sc = new Scanner(System.in);
static int N = 110;
static int[][] dp = new int[N][N];
static int Inf = 0x3f3f3f3f;
static int n = 0;
static int[][] w = new int[N][N];
public static void main(String[] args) {
n = sc.nextInt();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
w[i][j] = sc.nextInt();
}
}
//注意必須從0開始賦值
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
dp[i][j] = Inf;
}
}
dp[1][1] = w[1][1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = Math.min(dp[i][j],dp[i][j - 1] + w[i][j]);
dp[i][j] = Math.min(dp[i][j],dp[i - 1][j] + w[i][j]);
}
}
System.out.println(dp[n][n]);
}
}
法二：記憶化搜索
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = 110;
static int[][] f = new int[N][N];
static int Inf = 0x3f3f3f3f;
static int n = 0;
static int[][] w = new int[N][N];
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
for(int i = 1; i <= n; i++) {
String[] ww = br.readLine().split(" ");
for(int j = 1; j <= n; j++) {
w[i][j] = Integer.parseInt(ww[j - 1]);
}
}
// for(int i = 0; i < N; i++) {
// for(int j = 0; j < N; j++) {
// f[i][j] = -1;
// }
// }
int ans = dfs(n,n);
System.out.println(ans);
}
private static int dfs(int x, int y) {
if(f[x][y] != 0) {
return f[x][y];
}
if(x == 1 && y == 1) {
f[x][y] = w[x][y];
return f[x][y];
}
if(x < 1 || y < 1) {
return Inf;
}
int t = Inf;
t = Math.min(t,dfs(x - 1,y) + w[x][y]);
t = Math.min(t,dfs(x, y - 1) + w[x][y]);
return f[x][y] = t;
}
}
方格取數(shù)（線性DP）
此題和上面的dp差不多，也是從左上角到右下角，但是需要注意點(diǎn)餓是我們需要找到兩條路徑的最大和，第一感覺是進(jìn)行兩次上面的操作，但是是不可以的，因?yàn)闆]走過一點(diǎn)會(huì)置為0，當(dāng)我們選定了第一條路徑后，第一條路徑走過的地方會(huì)置為0，我們?cè)诘诙芜M(jìn)行時(shí)，并不能保證此種選擇是兩條路徑之和最大的。
設(shè)dp[i][j][p][q]為兩條路徑分別從起點(diǎn)到i,j和p,q的路徑的最大和。
需要注意的是如果我們到達(dá)同一點(diǎn)的時(shí)候，會(huì)導(dǎo)致同一點(diǎn)的數(shù)被取了兩遍，此時(shí)我們需要減去一次，注意我們是在所有情況中取的最大值，只有在走到同一點(diǎn)的時(shí)候才會(huì)重復(fù)取兩次。
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = 12;
static int[][][][] dp = new int[N][N][N][N];
static int[][] a = new int[N][N];
static int n = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
while(true) {
String[] xyz = br.readLine().split(" ");
int x = Integer.parseInt(xyz[0]);
int y = Integer.parseInt(xyz[1]);
int z = Integer.parseInt(xyz[2]);
if(x == 0 && y == 0 && z == 0) {
break;
}
a[x][y] = z;
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
for (int p = 1; p <= n; p ++) {
for (int q = 1; q <= n; q ++) {
dp[i][j][p][q] = Math.max(dp[i][j][p][q], dp[i-1][j][p-1][q]+a[i][j]+a[p][q]);
dp[i][j][p][q] = Math.max(dp[i][j][p][q], dp[i-1][j][p][q-1]+a[i][j]+a[p][q]);
dp[i][j][p][q] = Math.max(dp[i][j][p][q], dp[i][j-1][p-1][q]+a[i][j]+a[p][q]);
dp[i][j][p][q] = Math.max(dp[i][j][p][q], dp[i][j-1][p][q-1]+a[i][j]+a[p][q]);
if (i == p && j == q) {
dp[i][j][p][q] -= a[i][j];
// System.out.println(111);
}
}
}
}
}
System.out.println(dp[n][n][n][n]);
}
}
傳紙條
此題目和上面的方格取數(shù)基本是一樣的。
此題目描述是：從左上角傳到右下角和從右下角傳到左上角各一次，但是此是一個(gè)點(diǎn)不能重復(fù)走兩次（和上面的方格取數(shù)的走完會(huì)清零不同），首先，我們可以轉(zhuǎn)換為都是從左上角開始向右下角同時(shí)開始，此時(shí)和方格取數(shù)差不多了）
??重點(diǎn)需要理解的是：
方格取數(shù)是可以兩次重復(fù)走到一個(gè)地方，但是最優(yōu)解肯定不會(huì)走相同的地方。
本題是不可以走相同的地方。
經(jīng)過轉(zhuǎn)換后，所以兩道題的代碼基本是一樣的。
下面的證明是從大佬的題解看到的大佬題解對(duì)于沒有交點(diǎn)的情況，我們不需要考慮。 主要是證明為什么不會(huì)取到走到同一點(diǎn)的情況。
比如上方紅色是A路線，綠色是B路線。 存在相交的地方，我們只需要交換路線即可，對(duì)答案并沒有任何影響。
用橙色代表與綠色交換后的紅色，用亮綠色代表與紅色交換后的綠色，可以得到如下路線：
但是很明顯可以看到還是有同時(shí)走到的點(diǎn)，但是由于
這個(gè)條件，我們可以知道繞路走的
話肯定是比走同一個(gè)點(diǎn)更優(yōu)。我們可以尋找綠色繞路或者藍(lán)色繞路的最優(yōu)值。
最長上升子序列模型
怪盜基德的滑翔翼（線性DP、LIS）
很明顯就是最長上升子序列，它可以選擇從最高樓層的頂部開始進(jìn)行下落。但是題目中說了它可以從任何一個(gè)樓開始，但是開始后就不能改變方向，所以有兩種情況：
（1）從左到右，最高的在右邊，然后我們需要求的就是最長上升子序列（對(duì)應(yīng)于樣例中的2、3）需要求最長上升子序列
（2）從右往左飛，最高的在左邊，我們需要求得就是最長下降子序列，但是本質(zhì)都是一樣的，進(jìn)行兩次即可。
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = 110;
static int[] h = new int[N];
static int[] dp = new int[N]; //最長上升子序列
static int[] dp2 = new int[N]; //最長下降子序列
static int k = 0, n = 0;
public static void main(String[] args) throws Exception{
k = Integer.parseInt(br.readLine());
while(k-- > 0) {
n = Integer.parseInt(br.readLine());
String[] hh = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
h[i] = Integer.parseInt(hh[i - 1]);
}
for(int i = 1; i <= n; i++) {
dp[i] = 1;
for(int j = 1; j < i; j++) {
if(h[j] < h[i]) {
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = Math.max(dp[i],ans);
}
for(int i = 1; i <= n; i++) {
dp2[i] = 1;
for(int j = 1; j < i; j++) {
if(h[j] > h[i]) {
dp2[i] = Math.max(dp2[i],dp2[j] + 1);
}
}
}
for(int i = 1; i <= n; i++) {
ans = Math.max(dp2[i],ans);
}
System.out.println(ans);
}
}
}
對(duì)于第一種情況：就是求最長上升子序列；
第二種情況：就是求最長下降子序列；
第三種情況：就是求最長上升子序列和最長下降子序列的最大值。
綜上，我們只需要求解最長上升子序列和最長下降子序列的最大值。
登山（線性DP、LIS模板題）
第一次看題覺得和上面的差不多，但是需要注意，此題是可以下山，就是下山的過程中也是可以看的，我們需要求得是兩者的和，
但是我們需要注意的是，up和down是有區(qū)別的，和上一題不同，因?yàn)槲覀兦笞铋L上升子序列的時(shí)候，求得是以i為結(jié)尾的最長上升子序列，那么如果我們對(duì)于down和up都這樣求得話肯定是不行的，我們需要稍微改變一下down[]的定義：
up[i]：以i為結(jié)尾的最長上升子序列
down[i]:以i為開頭的最長下降子序列。
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = 1100;
static int[] h = new int[N];
static int[] up = new int[N]; //最長上升子序列
static int[] down = new int[N];
static int k = 0, n = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
String[] hh = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
h[i] = Integer.parseInt(hh[i - 1]);
}
for(int i = 1; i <= n; i++) {
up[i] = 1;
for(int j = 1; j < i; j++) {
if(h[j] < h[i]) {
up[i] = Math.max(up[i],up[j] + 1);
}
}
}
//down[i]代表以i為左端點(diǎn)的最長下降子序列
for(int i = n; i >= 1; i--) {
down[i] = 1;
for(int j = n; j > i; j--) {
if(h[i] > h[j]) {
down[i] = Math.max(down[i],down[j] + 1);
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = Math.max(ans,up[i] + down[i] - 1);
// System.out.println(i + " " + up[i] + " " + down[i] + " " + ans);
}
System.out.println(ans);
}
}
合唱隊(duì)形(LIS 線性DP)
和上面上面的登山可以說是完全一樣，只是此題需要輸出n-ans
很明顯我們通過上面的代碼可以求出最長上升和最長下降的和的最大，即為最后合照剩下的人，那么需要出列的人數(shù)肯定就是原來的總?cè)藬?shù)-最后剩下的人。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = 1100;
static int[] h = new int[N];
static int[] up = new int[N]; //最長上升子序列
static int[] down = new int[N];
static int k = 0, n = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
String[] hh = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
h[i] = Integer.parseInt(hh[i - 1]);
}
for(int i = 1; i <= n; i++) {
up[i] = 1;
for(int j = 1; j < i; j++) {
if(h[j] < h[i]) {
up[i] = Math.max(up[i],up[j] + 1);
}
}
}
//down[i]代表以i為左端點(diǎn)的最長下降子序列
for(int i = n; i >= 1; i--) {
down[i] = 1;
for(int j = n; j > i; j--) {
if(h[i] > h[j]) {
down[i] = Math.max(down[i],down[j] + 1);
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = Math.max(ans,up[i] + down[i] - 1);
// System.out.println(i + " " + up[i] + " " + down[i] + " " + ans);
}
System.out.println(n - ans);
}
}
友好城市（LIS優(yōu)化版+模型轉(zhuǎn)換）????
這題需要通過畫圖去轉(zhuǎn)換，否則很難直接看出來：
很明顯紅色的是不可以的，綠色這種建橋方式是可行的。 我們可以看到只要兩岸的城市都保證是上升子序列即可。 但是他們之間存在各自的一對(duì)一關(guān)系，起初想著分別求LIS，然后求兩者最小值的最大值，這種方法是不可行的，主要是我們需要保證他們之間的對(duì)應(yīng)關(guān)系。
那么我們可以通過一邊對(duì)這對(duì)對(duì)應(yīng)關(guān)系進(jìn)行排序，然后再對(duì)另一邊求最長上升子序列即為答案。
畫圖理解比較直觀一點(diǎn)：
上面的兩種情況都是可以的，所以最終答案就為4
題目理解完畢，開始寫代碼（主要就是LIS）
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (2e5 + 10);
static node[] info = new node[N];
static int[] dp = new int[N]; //最長上升子序列
static int k = 0, n = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
for(int i = 1; i <= n; i++) {
String[] xy = br.readLine().split(" ");
info[i] = new node();
info[i].x = Integer.parseInt(xy[0]);
info[i].y = Integer.parseInt(xy[1]);
}
Arrays.sort(info,1, 1 + n, new cmp());
for(int i = 1; i <= n; i++) {
dp[i] = 1;
for(int j = 1; j < i; j++) {
if(info[j].y < info[i].y) {
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
}
int ans =0;
for(int i = 1; i <= n; i++) {
ans = Math.max(ans,dp[i]);
}
System.out.println(ans);
}
}
class node{
int x,y;
}
class cmp implements Comparator<node>{
@Override
public int compare(node o1, node o2) {
return o1.x - o2.x;
}
}
顯然上面的代碼時(shí)間復(fù)雜度為O(n2)
顯然是過不了的，那么我們就需要使用二分優(yōu)化的LIS（Nlogn）
主要思想就是，在滿足最長上升子序列的前提下，盡可能增大結(jié)尾的潛能
使用q[]數(shù)組存儲(chǔ)所有不同長度的上升子序列的結(jié)尾的最小值。
每加進(jìn)來一個(gè)數(shù)，通過在q中查找最大的小于ai的數(shù)，并將ai接上去，q[r+1]=a[i]
下面可以略：主要解釋LIS的原理：
?
主要是因?yàn)?，能接在更小的?shù)后面的數(shù)肯定更多
比較繞的一點(diǎn)是，如果此時(shí)加入的數(shù)比結(jié)尾小，我們需要在q中查找大于等于它的數(shù)去替換，那么可能出現(xiàn)我們這個(gè)數(shù)比后買你的下標(biāo)大 比如1 2 78
此時(shí)來了個(gè)5，我們需要用5替換7.但是顯然5的下標(biāo)肯定比7的大，但是這對(duì)于僅僅求最長上升子序列的長度是沒有影響的，因?yàn)?后面的數(shù)的下標(biāo)肯定是都大于5的，假如5后面沒有數(shù)了，那么此時(shí)1
2 58
在序列里，所有最終答案為4，其實(shí)可以看作和5個(gè)7沒有環(huán)保是等價(jià)的，我們將7換為5只是為了給后面造成更大的機(jī)會(huì)，比如5后買還有6，7，那么此時(shí)1
2 5 8，6進(jìn)來找到8，進(jìn)行替換為1 2 5 6然后7直接放后面 12 5 6
7這樣就會(huì)比之前5和7不換序列更長。需要仔細(xì)體會(huì)！??！確實(shí)比較繞。
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (2e5 + 10);
static node[] info = new node[N];
static int k = 0, n = 0;
static int[] q = new int[N];
static int cnt = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
for(int i = 1; i <= n; i++) {
String[] xy = br.readLine().split(" ");
info[i] = new node();
info[i].x = Integer.parseInt(xy[0]);
info[i].y = Integer.parseInt(xy[1]);
}
Arrays.sort(info,1, 1 + n, new cmp());
// for(int i = 1; i <= n; i++) {
// dp[i] = 1;
// for(int j = 1; j < i; j++) {
// if(info[j].y < info[i].y) {
// dp[i] = Math.max(dp[i],dp[j] + 1);
// }
// }
// }
q[++cnt] = info[1].y;
for(int i = 2; i <= n; i++) {
if(info[i].y > q[cnt]) {
q[++cnt] = info[i].y;
}else {
int tmp = find(info[i].y);
q[tmp] = info[i].y;
}
}
System.out.println(cnt);
}
//找最大的小于x的數(shù):找>=x的第一個(gè)數(shù)
private static int find(int x) {
int l = 1, r = cnt;
int res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(q[mid] >= x) {
res = mid;
r = mid - 1;
}else {
l = mid + 1;
}
}
return res;
}
}
class node{
int x,y;
}
class cmp implements Comparator<node>{
@Override
public int compare(node o1, node o2) {
return o1.x - o2.x;
}
}
完美AC！
最大上升子序列和
本質(zhì)還是最長上升子序列，此時(shí)代表的是： dp[i]代表以a[i]結(jié)尾最大上升子序列和，
當(dāng)a[j] < a[i]時(shí)候，我們改變之前的+1，為加當(dāng)前這個(gè)數(shù)，注意是a[i]不是a[j]
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (2e5 + 10);
static int[] dp = new int[N]; //最長上升子序列
static int k = 0, n = 0;
static int[] q = new int[N];
static int cnt = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
String[] aa = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
q[i] = Integer.parseInt(aa[i - 1]);
}
for(int i = 1; i <= n; i++) {
dp[i] = q[i];
for(int j = 1; j < i; j++){
if(q[j] < q[i]) {
dp[i] = Math.max(dp[i], dp[j] + q[i]);
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = Math.max(ans,dp[i]);
}
System.out.println(ans);
}
}
攔截導(dǎo)彈（LIS/最長不上升子序列）
?
題目描述很明確，就是求最長不下降子序列，只需要改變求最長上升子序列時(shí)的轉(zhuǎn)移條件即可。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (2e5 + 10);
static int[] dp = new int[N]; //最長不上升子序列
static int k = 0, n = 0;
static int[] q = new int[N];
static int cnt = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
String[] aa = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
q[i] = Integer.parseInt(aa[i - 1]);
}
for(int i = 1; i <= n; i++) {
dp[i] = 1;
for(int j = 1; j < i; j++){
if(q[j] >= q[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = Math.max(ans,dp[i]);
}
System.out.println(ans);
}
}
導(dǎo)彈防御系統(tǒng)(DFS+線性DP?????)
?
最長公共上升子序列（??）
?
狀態(tài)機(jī)模型
大盜阿福(線性DP、狀態(tài)機(jī)??)
?
法一：分步轉(zhuǎn)移
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (1e5 + 10);
static int t = 0;
static int[] dp = new int[N];
static int[] w = new int[N];
static int n = 0;
public static void main(String[] args) throws IOException {
t = Integer.parseInt(br.readLine());
while(t-- > 0) {
n = Integer.parseInt(br.readLine());
String[] ww = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
w[i] = Integer.parseInt(ww[i - 1]);
}
dp[0] = 0;
dp[1] = w[1];
for(int i = 2; i <= n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + w[i]);
}
System.out.println(dp[n]);
}
}
}
法2：分類轉(zhuǎn)移
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (1e5 + 10);
static int t = 0;
static int[][] dp = new int[N][2];
static int[] w = new int[N];
static int n = 0;
public static void main(String[] args) throws IOException {
t = Integer.parseInt(br.readLine());
while(t-- > 0) {
n = Integer.parseInt(br.readLine());
String[] ww = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
w[i] = Integer.parseInt(ww[i - 1]);
}
dp[1][0] = 0;
dp[1][1] = w[1];
for(int i = 2; i <= n; i++) {
//不偷第i家，那么第i-1家可以選擇偷，也可以不偷
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + w[i]; //偷第i家
}
System.out.println(Math.max(dp[n][0],dp[n][1]));
}
}
}
買賣股票的最佳時(shí)機(jī) II
?
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < n; i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
}
// System.out.println(prices[0]);
return dp[n - 1][0];
}
}
股票買賣 IV
?
下面的代碼只能過50%，我們需要使用滾動(dòng)數(shù)組進(jìn)行空間優(yōu)化
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (1e5 + 10);
static int t = 0;
static int[][][] dp = new int[N][110][2]; //i天j次交易，手中是否有票
static int[] prices = new int[N];
static int n = 0,k = 0;
static int Inf = 0x3f3f3f3f;
public static void main(String[] args) throws IOException {
String[] nk = br.readLine().split(" ");
n = Integer.parseInt(nk[0]);
k = Integer.parseInt(nk[1]);
// System.out.println(n +" " + k);
String[] p = br.readLine().split(" ");
// System.out.println(p.length);
for(int i = 1; i <= n; i++) {
prices[i] = Integer.parseInt(p[i - 1]);
}
for(int j = 0; j <= k; j++) {
dp[0][j][1] = -Inf; //0天j筆交易手中郵票是無效狀態(tài)，本題求max,所以初始化為-inf
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
}
}
System.out.println(dp[n][k][0]); //第n天進(jìn)行k次交易手中無票
}
}
AC代碼：
因?yàn)閒[i][][]只用到了f[i-1][[]去更新，所以可以將最外層優(yōu)化掉文章來源：http://www.zghlxwxcb.cn/news/detail-447032.html
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (1e5 + 10);
static int t = 0;
static int[][] dp = new int[110][2]; //i天j次交易，手中是否有票
static int[] prices = new int[N];
static int n = 0,k = 0;
static int Inf = 0x3f3f3f3f;
public static void main(String[] args) throws IOException {
String[] nk = br.readLine().split(" ");
n = Integer.parseInt(nk[0]);
k = Integer.parseInt(nk[1]);
// System.out.println(n +" " + k);
String[] p = br.readLine().split(" ");
// System.out.println(p.length);
for(int i = 1; i <= n; i++) {
prices[i] = Integer.parseInt(p[i - 1]);
}
for(int j = 0; j <= k; j++) {
dp[j][1] = -Inf; //0天j筆交易手中郵票是無效狀態(tài)，本題求max,所以初始化為-inf
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
dp[j][0] = Math.max(dp[j][0],dp[j][1]+prices[i]);
dp[j][1] = Math.max(dp[j][1],dp[j-1][0]-prices[i]);
}
}
System.out.println(dp[k][0]); //第n天進(jìn)行k次交易手中無票
}
}
股票買賣 V（含冷凍期）
?
文章來源地址http://www.zghlxwxcb.cn/news/detail-447032.html
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (1e5 + 10);
static int t = 0;
static int[][] dp = new int[N][3]; //i天j次交易，手中是否有票
static int[] prices = new int[N];
static int n = 0,k = 0;
static int Inf = 0x3f3f3f3f;
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
String[] p = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
prices[i] = Integer.parseInt(p[i - 1]);
}
dp[0][1] = -Inf;
dp[0][0] = -Inf;
dp[0][2] = 0;
for(int i = 1; i <= n; i++) {
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2] - prices[i]);
dp[i][0] = dp[i-1][1] + prices[i];
dp[i][2] = Math.max(dp[i-1][0],dp[i-1][2]);
}
System.out.println(Math.max(dp[n][0],dp[n][2]));
}
}
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃專題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
