IVN
0%

DP-3

Posted on Edited on In
Symbols count in article: 18k Reading time ≈ 17 mins.

DP选编（3）

265. Paint House II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int minCostII(int[][] costs) {
    int k=costs[0].length;
    int n=costs.length;
    int[][] dp=new int[n][k];
    for (int i = 0; i < k; i++) {
        dp[0][i]=costs[0][i];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < k; j++) {
            int min=Integer.MAX_VALUE;
            for (int p = 0; p < k; p++) {
                if(p==j){
                    continue;
                }
                min=Math.min(min,dp[i-1][p]);
            }
            dp[i][j]=costs[i][j]+min;
        }
    }
    int res=Integer.MAX_VALUE;
    for (int i = 0; i < k; i++) {
        res=Math.min(res,dp[n-1][i]);
    }
    return res;
}

Follow up: Could you solve it in O(nk) runtime?

276. Paint Fence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int numWays(int n, int k) {
    if(n==1){
        return k;
    }
    if(n==2){
        return k*k;
    }
    int[] dp=new int[n+1];
    dp[1]=k;
    dp[2]=k*k;
    for (int i = 3; i < n; i++) {
        //not same + same
        //dp[i-1]*(k-1) + not same(i-2,i-1)*1
        dp[i]=(dp[i-1]+dp[i-2])*(k-1);
    }
    return dp[n];
}

651. 4 Keys Keyboard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxA(int n) {
    if(n<=3){
        return n;
    }
    int[] dp=new int[n+1];
    dp[1]=1;
    dp[2]=2;
    dp[3]=3;
    for (int i = 4; i <= n; i++) {
        //ctrlA,ctrlC,ctrlV
        dp[i]=i;
        int p=2;
        //inefficient to press ctrlV more than 5 times
        for (int j = i-3; j>=1; j--) {
            dp[i]=Math.max(dp[i],dp[j]*p);
            p++;
            if(p>=6){
                break;
            }
        }
    }
    return dp[n];
}

1259. Handshakes That Don’t Cross

1
2
3
4
5
6
7
8
9
10
11
12
13
public int numberOfWays(int numPeople) {
    int[] dp=new int[numPeople+1];
    dp[0]=1;
    int m=(int)1e9+7;
    for (int i = 2; i <= numPeople; i+=2) {
        for (int j = 0; j <= i-2; j+=2) {
            //j,2,i-j-2
            dp[i]+=(long)dp[j]*dp[i-2-j]%m;
            dp[i]%=m;
        }
    }
    return dp[numPeople];
}

1444. Number of Ways of Cutting a Pizza

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class LeetCode1444 {

    int mod=(int)1e9+7;
    int row;
    int col;
    int[][][] dp;
    int[][] sum; //number of apple in (i,j,row-1,col-1)
    public int ways(String[] pizza, int k) {
        row=pizza.length;
        col=pizza[0].length();
        sum=new int[row+1][col+1];
        for (int i = row-1; i >= 0; i--) {
            for (int j = col-1; j >= 0; j--) {
                sum[i][j]=sum[i+1][j]+sum[i][j+1]-sum[i+1][j+1]+
                        (pizza[i].charAt(j)=='A' ? 1 : 0);
            }
        }
        dp=new int[row][col][k+1];
        return dfs(0,0,k);
    }

    int dfs(int i, int j, int k){
        if(sum[i][j]==0){
            return 0;
        }
        if(k==1){
            return 1;
        }
        if(dp[i][j][k]!=0){
            return dp[i][j][k];
        }
        int res=0;
        //horizontal cut
        for (int x = i+1; x < row; x++) {
            if(sum[i][j]-sum[x][j]>0){
                res=(res+dfs(x,j,k-1))%mod;
            }
        }
        //vertical cut
        for (int y = j+1; y < col; y++) {
            if(sum[i][j]-sum[i][y]>0){
                res=(res+dfs(i,y,k-1))%mod;
            }
        }
        dp[i][j][k]=res;
        return res;
    }
}

983. Minimum Cost For Tickets

法一：dfs with memo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int[] days;
int[] costs;
Map<Integer,Integer> memo=new HashMap<>();
public int mincostTickets(int[] days, int[] costs) {
    this.days=days;
    this.costs=costs;
    return backtracking(0,0);
}

int backtracking(int i, int nextStart){
    if(i>=days.length || nextStart>days[days.length-1]){
        return 0;
    }
    if(memo.containsKey(i*365+nextStart)){
        return memo.get(i*365+nextStart);
    }
    //choose 1-day
    int choose1=costs[0];
    for (int j = i; j < days.length; j++) {
        if(days[j]<nextStart){
            continue;
        }
        choose1+=backtracking(j+1,days[j]+1);
        break;
    }
    //choose 7-day
    int choose7=costs[1];
    for (int j = i; j < days.length; j++) {
        if(days[j]<nextStart){
            continue;
        }
        choose7+=backtracking(j+1,days[j]+7);
        break;
    }
    //choose 30-day
    int choose30=costs[2];
    for (int j = i; j < days.length; j++) {
        if(days[j]<nextStart){
            continue;
        }
        choose30+=backtracking(j+1,days[j]+30);
        break;
    }
    int res=Math.min(Math.min(choose1,choose7),choose30);
    memo.put(i*365+nextStart,res)
    return res;
}

法二：dp with queue

https://leetcode.com/problems/minimum-cost-for-tickets/discuss/226659/Two-DP-solutions-with-pictures

同法一表现无异

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int mincostTickets(int[] days, int[] costs) {
    int n=days.length;
    int total=0;
    Deque<int[]> last7=new LinkedList<>();
    Deque<int[]> last30=new LinkedList<>();
    for (int i = 0; i < n; i++) {
        while(!last7.isEmpty() && last7.peek()[0]+7<=days[i]){
            last7.poll();
        }
        last7.offer(new int[]{days[i],total+costs[1]});
        while(!last30.isEmpty() && last30.peek()[0]+30<=days[i]){
            last30.poll();
        }
        last30.offer(new int[]{days[i],total+costs[2]});
        total=Math.min(total+costs[0],Math.min(last7.peek()[1],last30.peek()[1]));
    }
    return total;
}

法三：dp

注意：

  • dp数组长度并不由days数组长度决定，而是由lastday决定
  • 由于只需考虑前30天，可以进一步通过 mod30 来优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int mincostTickets(int[] days, int[] costs) {
            int[] dp = new int[30];
    int d = 0; // d means the index of next travel day
    int lastday = days[days.length - 1];
    
    for (int i = days[0]; i <= lastday; i++) {
        if (i != days[d]) dp[i % 30] = dp[(i - 1) % 30]; // we don't have thid day for travel, price as yesterday
        else { // i == days[d]
            dp[i % 30] = Math.min(dp[(i - 1) % 30] + costs[0], Math.min(dp[Math.max(i - 7, 0) % 30] + costs[1], dp[Math.max(i - 30, 0) % 30] + costs[2]));
            d++;
        }
    }
    
    
    return dp[lastday % 30];
}

790. Domino and Tromino Tiling

难以理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int numTilings(int n) {
            if(n==1)
    return 1;
    else if(n==2)
    return 2;
  int mod = 1000000007;

int [] dp=new int[n+1];

dp[1]=1;
dp[2]=2;
dp[3]=5;
for(int i =4;i<=n;i++){
    dp[i]=(2*dp[i-1]%mod+dp[i-3]%mod)%mod;
}
return dp[n];
}

勉强可以理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int numTilings(int n) {
    //f(k)=f(k-1)+f(k-2)+2*p(k-1)
    //p(k)=p(k-1)+f(k-2)

    if(n==1){
        return 1;
    }
    if(n==2){
        return 2;
    }
    int mod=(int)1e9+7;
    long[] f=new long[n+1];
    long[] p=new long[n+1];
    f[1]=1;
    f[2]=2;
    p[2]=1;
    for (int i = 3; i <= n; i++) {
        p[i]=(p[i-1]%mod+f[i-2]%mod)%mod;
        f[i]=(f[i-1]%mod+f[i-2]%mod+2*p[i-1]%mod)%mod;
    }
    return (int)f[n];
}

2218. Maximum Value of K Coins From Piles

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n;
int[][] dp;
List<List<Integer>> piles;
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
    n=piles.size();
    this.piles=piles;
    dp=new int[n][k+1];
    //use pile [i,n-1] to build max k elements
    return dp(0,k);
}

int dp(int i, int k){
    if(i>=n || k==0){
        return 0;
    }
    if(dp[i][k]!=0){
        return dp[i][k];
    }
    int max=dp(i+1,k);
    int cur=0;
    for(int j=0; j<Math.min(k,piles.get(i).size()); j++){
        cur+=piles.get(i).get(j);
        //j,k-j
        max=Math.max(max,cur+dp(i+1,k-j-1));
    }
    return dp[i][k]=max;
}

2140. Solving Questions With Brainpower

1
2
3
4
5
6
7
8
9
10
11
12
public long mostPoints(int[][] questions) {
    int n=questions.length;
    //most points starting from i
    long[] dp=new long[n];
    dp[n-1]=questions[n-1][0];
    for (int i = n-2; i >= 0; i--) {
        int next=i+questions[i][1]+1;
        dp[i]=Math.max(dp[i+1],
                questions[i][0]+(next<n? dp[next] : 0));
    }
    return dp[0];
}

1547. Minimum Cost to Cut a Stick

https://leetcode.com/problems/minimum-cost-to-cut-a-stick/discuss/781074/JavaC%2B%2BPython-Merge-Stones

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minCost(int n, int[] cuts) {
    List<Integer> list=new ArrayList<>();
    list.add(0);
    list.add(n);
    for (int cut : cuts) {
        list.add(cut);
    }
    Collections.sort(list);
    int k=list.size();
    int[][] dp=new int[k][k];
    for(int d=2; d<k; d++){
        for(int i=0; i+d<k; i++){
            dp[i][i+d]=Integer.MAX_VALUE;
            for(int m=i+1; m<i+d; m++){
                dp[i][i+d]=Math.min(dp[i][i+d],
                        dp[i][m]+dp[m][i+d]+list.get(i+d)-list.get(i));
            }
        }
    }
    return dp[0][k-1];
}

2328. Number of Increasing Paths in a Grid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public int countPaths(int[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    int mod=(int)1e9+7;
    int[] dx=new int[]{0,0,1,-1};
    int[] dy=new int[]{1,-1,0,0};
    long[][] dp=new long[row][col]; //path ending with [i,j]
    TreeMap<Integer, List<int[]>> map=new TreeMap<>();
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            map.putIfAbsent(grid[i][j],new ArrayList<>());
            map.get(grid[i][j]).add(new int[]{i,j});
        }
    }
    long res=0;
    for (Integer val : map.keySet()) {
        for (int[] arr : map.get(val)) {
            int i=arr[0];
            int j=arr[1];
            dp[i][j]=1;
            for (int k = 0; k < 4; k++) {
                int x=i+dx[k];
                int y=j+dy[k];
                if(x>=0 && x<row && y>=0 && y<col
                        && grid[x][y]<val){
                    dp[i][j]+=dp[x][y];
                    dp[i][j]%=mod;
                }
            }
            res+=dp[i][j];
            res%=mod;
        }
    }
    return (int)res;
}

2742. Painting the Walls

0/1 knapsack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int paintWalls(int[] cost, int[] time) {
    int n=cost.length;
    int[] dp=new int[n+1]; //minimum cost to paint n walls
    Arrays.fill(dp,(int)1e9);
    //use cost[0,i] to paint n walls
    //choose, not choose
    //dp[i][n] = Math.min(dp[i-1][n], cost[i]+dp[i-1][n-time[i]-1])
    for (int i = 0; i < n; i++) {
        for (int j = n; j > 0; j--) {
            dp[j]=Math.min(dp[j],
                    cost[i] + (j-time[i]-1>0 ? dp[j-time[i]-1] :0));
        }
    }
    return dp[n];
}

1575. Count All Possible Routes

What’s the state of each sub problem?

What’s the base case?

What’s the state transfer equation?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int mod=(int)1e9+7;
int[][] dp;
int finish;
int[] locations;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
    int n=locations.length;
    dp=new int[n][fuel+1];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i],-1);
    }
    dp[finish][0]=1;
    this.locations=locations;
    this.finish=finish;
    return dfs(start,fuel);
}

private int dfs(int start, int fuel){
    if(fuel<0){
        return 0;
    }
    if(dp[start][fuel]!=-1){
        return dp[start][fuel];
    }
    if(fuel==0){
        return 0;
    }
    int res= start==finish ? 1 : 0;
    for (int i = 0; i < locations.length; i++) {
        if(i==start){
            continue;
        }
        res=(res+dfs(i,fuel-Math.abs(locations[start]-locations[i])))%mod;
    }
    return dp[start][fuel]=res;
}

1723. Find Minimum Time to Finish All Jobs

https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs/discuss/1009817/One-branch-cutting-trick-to-solve-three-LeetCode-questions

思路：

  • similar to 698. Partition to K Equal Sum Subsets
  • DFS + optimization(branch cutting)
    • assign the most time consuming job first
    • avoid duplicated search (same scenario)
    • avoid meaningless search (>=res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int res=Integer.MAX_VALUE;
int[] workers;
int n;
int k;
public int minimumTimeRequired(int[] jobs, int k) {
    Arrays.sort(jobs);
    workers=new int[k];
    n=jobs.length;
    this.k=k;
    dfs(jobs,n-1,0);
    return res;
}

private void dfs(int[] jobs, int cur, int preMax){
    if(cur==-1){
        res=Math.min(res,preMax);
        return;
    }
    for (int i = 0; i < k; i++) {
        boolean skip=false;
        for (int j = 0; j < i; j++) {
            if(workers[i]==workers[j]){
                skip=true;
                break;
            }
        }
        if(!skip && workers[i]+jobs[cur]<res){
            workers[i]+=jobs[cur];
            dfs(jobs,cur-1,Math.max(preMax,workers[i]));
            workers[i]-=jobs[cur];
        }
    }
}

1751. Maximum Number of Events That Can Be Attended II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int n;
int[][] dp;
int[][] events;
public int maxValue(int[][] events, int k) {
    this.events=events;
    n=events.length;
    dp=new int[n][k+1];
    for (int[] arr : dp) {
        Arrays.fill(arr,-1);
    }
    Arrays.sort(events,(a,b)->(a[0]!=b[0] ? a[0]-b[0] : a[1]-b[1]));
    return dfs(0,k);
}


private int dfs(int i, int k){
    if(i==-1 || i==n || k==0){
        return 0;
    }
    if(dp[i][k]!=-1){
        return dp[i][k];
    }
    //not choose
    int c1=dfs(i+1,k);
    //choose
    int next=binarySearch(i);
    int c2=events[i][2]+dfs(next,k-1);
    return dp[i][k]=Math.max(c1,c2);
}

private int binarySearch(int cur){
    //next available event
    //first(smallest) event with start >= curEnd
    int left=cur+1;
    int right=n;
    int mid=0;
    int curEnd=events[cur][1];
    while(left<right){
        //[left,right)
        mid=(left+right)/2;
        //not valid
        if(events[mid][0]<=curEnd){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

2361. Minimum Costs Using the Train Line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public long[] minimumCosts(int[] regular, int[] express, int expressCost) {
    int n=regular.length;
    long[] res=new long[n];
    //min cost to reach i-1 by regular/express
    long[][] dp=new long[n][2];
    dp[0][0]=regular[0];
    dp[0][1]=expressCost+express[0];
    res[0]=Math.min(dp[0][0],dp[0][1]);
    for (int i = 1; i < n; i++) {
        //regular -> regular
        //regular -> express
        //express -> regular
        //express -> express
        dp[i][0]=Math.min(dp[i-1][0]+regular[i],dp[i-1][1]+regular[i]);
        dp[i][1]=Math.min(dp[i-1][0]+expressCost+express[i],dp[i-1][1]+express[i]);
        res[i]=Math.min(dp[i][0],dp[i][1]);
    }
    return res;
}

664. Strange Printer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int n;
int[][] dp;
public int strangePrinter(String s) {
    n=s.length();
    dp=new int[n][n];//minimum number of turns
    // to solve s[l,r] difference
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i],-1);
    }
    return dfs(s,0,n-1)+1;
}

private int dfs(String s, int l, int r){
    if(dp[l][r]!=-1){
        return dp[l][r];
    }
    int res=n;
    int j=-1;//first different element than s[r]
    for(int i=l;i<r; i++){
        if(s.charAt(i)!=s.charAt(r) && j==-1){
            j=i;
        }
        if(j!=-1){
            //s[l,j-1] is the same as s[r], no need to solve
            //need 1 extra move to print all to s[r]
            //try all possible i
            res=Math.min(res,dfs(s,j,i)+dfs(s,i+1,r)+1);
        }
    }
    if(j==-1){
        res=0;
    }
    return dp[l][r]=res;
}

808. Soup Servings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Map<Integer, Map<Integer,Double>> map;
public double soupServings(int n) {
    //edge case, when n is large enough, p is almost 1
    if(n>=5000){
        return 1.0;
    }
    map=new HashMap<>();
    return dfs(n,n);
}

private double dfs(int a, int b){
    if(a<=0 && b<=0){
        return 0.5;
    }
    if(a<=0){
        return 1;
    }
    if(b<=0){
        return 0;
    }
    if(map.containsKey(a) && map.get(a).containsKey(b)){
        return map.get(a).get(b);
    }
    double res=0;
    //100 0
    res+=0.25*dfs(a-100,b);
    //75 25
    res+=0.25*dfs(a-75,b-25);
    //50 50
    res+=0.25*dfs(a-50,b-50);
    //25 75
    res+=0.25*dfs(a-25,b-75);
    map.putIfAbsent(a,new HashMap<>());
    map.get(a).put(b,res);
    return res;
}

920. Number of Music Playlists

思路：

  • fill i spots with j unique songs
    • option 1: already know i-1, j-1, can simply choose another song from other n-j+1 songs, and append it
    • option 2: try to append an old song, and this song cannot appear in interval [i-k,i-1] => k old songs in this interval should not be considered
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int n;
int k;
int[][] dp;
int mod=(int)1e9+7;
public int numMusicPlaylists(int n, int goal, int k) {
    this.n=n;
    this.k=k;
    dp=new int[goal+1][n+1];//fill goal spots with exactly n songs
    for (int i = 0; i <= goal; i++) {
        Arrays.fill(dp[i],-1);
    }
    return (int)dfs(goal,n);
}

private long dfs(int spots, int songs){
    if(spots==0 && songs==0){
        //one way to fill 0 spot using exactly 0 song
        return 1;
    }
    if(spots==0 || songs==0){
        //no way to fill some with exactly 0,
        // nor fill 0 with exactly some
        return 0;
    }
    if(dp[spots][songs]!=-1){
        return dp[spots][songs];
    }
    //already fill spots-1 with exactly songs-1, only need to append
    //one other song
    long res=dfs(spots-1,songs-1)*(n-songs+1)%mod;
    if(songs-k>0){
        //append an old song, choosing from songs except k
        //because songs in [i-k,i-1] must be unique and must not be chosen
        res+=dfs(spots-1,songs)*(songs-k)%mod;
        res%=mod;
    }
    return dp[spots][songs]=(int)res;
}

2369. Check if There is a Valid Partition For The Array

每个子问题只考察开头即可，开头不符合直接剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int n;
int[] dp; //[i,n-1] is valid or not
public boolean validPartition(int[] nums) {
    n=nums.length;
    dp=new int[n];
    return dfs(nums,0);
}

private boolean dfs(int[] nums, int start){
    if(start==n){
        return true;
    }
    if(dp[start]!=0){
        return start==1;
    }
    boolean res=false;
    if(start+2<n && nums[start]==nums[start+1] && nums[start]==nums[start+2]){
        res|=dfs(nums,start+3);
    }
    if(start+1<n && nums[start]==nums[start+1]){
        res|=dfs(nums,start+2);
    }
    if(start+2<n && nums[start]+1==nums[start+1] && nums[start]+2==nums[start+2]){
        res|=dfs(nums,start+3);
    }
    dp[start]=res ? 1 : -1;
    return res;
}

2707. Extra Characters in a String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int n;
int[] dp; //min extra char number in [i,n-1]
public int minExtraChar(String s, String[] dictionary) {
    Set<String> set=new HashSet<>();
    for (String s1 : dictionary) {
        set.add(s1);
    }
    n=s.length();
    dp=new int[n];
    Arrays.fill(dp,-1);
    return dfs(s,set,0);
}

private int dfs(String s, Set<String> set, int start){
    if(start==n){
        return 0;
    }
    if(dp[start]!=-1){
        return dp[start];
    }
    int res=Integer.MAX_VALUE;
    for (int i = start; i < n; i++) {
        //[start,i] [i+1,n-1]
        int sub=dfs(s,set,i+1);
        if(set.contains(s.substring(start,i+1))){
            res=Math.min(res,sub);
        }else{
            res=Math.min(res,sub+i-start+1);
        }
    }
    return dp[start]=res;
}

403. Frog Jump

法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int[] stones;
int[][] dp=new int[2000][2000];//curIdx, preStep
Map<Integer,Integer> map=new HashMap<>(); //stonePos to idx
int n;
public boolean canCross(int[] stones) {
    this.stones=stones;
    n=stones.length;
    for (int i = 0; i < n; i++) {
        map.put(stones[i],i);
    }
    for (int[] arr : dp) {
        Arrays.fill(arr,-1);
    }
    return dfs(0,1);
}

private boolean dfs(int curIdx, int preStep){
    if(curIdx==n-1){
        return true;
    }
    if(dp[curIdx][preStep]!=-1){
        return dp[curIdx][preStep]==1;
    }
    int curPos=stones[curIdx];
    boolean res=false;
    for(int i=preStep-1; i<=preStep+1; i++){

        if(i>0 && map.containsKey(curPos+i)){
            res|=dfs(map.get(curPos+i),i);
        }
    }
    dp[curIdx][preStep]=(res?1:0);
    return res;
}

法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public boolean canCross(int[] stones) {
    int n=stones.length;
    if(stones[1]!=1){
        return false;
    }
    Map<Integer,Set<Integer>> map=new HashMap<>();
    for (int stone : stones) {
        map.put(stone,new HashSet<>());
    }

    Deque<int[]> q=new LinkedList<>();
    map.remove(0);
    map.remove(1);
    q.offer(new int[]{1,1});
    while(!q.isEmpty()){
        int[] cur=q.poll();
        int idx=cur[0];
        int k=cur[1];
        if(idx==stones[n-1]){
            return true;
        }
        for(int p=-1; p<=1; p++){
            if(k+p>0){
                if(map.containsKey(idx+k+p) && !map.get(idx+k+p).contains(k+p)){
                    q.offer(new int[]{idx+k+p,k+p});
                    map.get(idx+k+p).add(k+p);
                }
            }
        }
    }
    return false;
}

377. Combination Sum IV

法一：top-down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int n;
Map<Integer,Integer> map=new HashMap<>();
public int combinationSum4(int[] nums, int target) {
    Arrays.sort(nums);
    n=nums.length;
    return dfs(nums,target);
}

int dfs(int[] nums,  int target){
    if(target<=0){
        if(target==0){
            return 1;
        }
        return 0;
    }
    if(map.containsKey(target)){
        return map.get(target);
    }
    int res=0;
    for (int i = 0; i < n; i++) {
        if(target-nums[i]<0){
            break;
        }
        res+=dfs(nums,target-nums[i]);
    }
    map.put(target,res);
    return res;
}

法二：bottom-up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int combinationSum4(int[] nums, int target) {
    int n=nums.length;
    int[] dp=new int[target+1]; //how many ways to reach target
    Arrays.sort(nums);
    dp[0]=1;
    for(int i=1; i<=target; i++){
        for(int num: nums){
            if(i-num<0){
                break;
            }
            dp[i]+=dp[i-num];
        }
    }
    return dp[target];
}