dp

发表于

Leetcode

70. 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?

Note: Given n will be a positive integer.

Example 1:

1
2
3
4
5
6
Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
7
Input: 3
Output:  3
Explanation:  There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

递归版本

1
2
3
4
5
6
7
8
9
class Solution {
    public int climbStairs(int n) {
        if(n == 0 || n == 1){
            return 1;
        }
        
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

dp版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
        
    public int climbStairs(int n) {
        
        int []A = new int[n+1];
        A[0] = 1;
        A[1] = 1;
        
        for(int i = 2; i <= n; ++i){
            A[i] = A[i-1] + A[i-2];    
        }
        
        return A[n];
    }
}

120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Example:

1
2
3
4
5
6
7
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

解题思路:

自底向上的搜索并记录最小的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int []A = new int[triangle.size()+1];
        
        for(int i = triangle.size()-1; i >= 0; --i){
            List<Integer> row = triangle.get(i);
            
            for(int j = 0; j < row.size(); ++j){
                A[j] = Math.min(A[j], A[j+1]) + row.get(j);
            }
        }
        
        return A[0];
    }
}

64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note:

You can only move either down or right at any point in time.

Example:

1
2
3
4
5
6
[
 [1,3,1],
 [1,5,1],
 [4,2,1]
]
 Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

解题思路:

1
2
3
4
5
6
7
8
9
在2X2数组中，从1到4的最小路径只有一条，1 -> 2 -> 4
在1+2+4和1+3+4的比较之后选取的最小值可得
[
	[1, 2],
	[3, 4]
]
依次可类推，除了第一行和第一列之后
所有待处理的元素，都是从上和左中选择最小的元素
直到元素[m-1, n-1]，每次选择的都是最小元素累加得到的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(i != 0 && j != 0){
                    grid[i][j] = Math.min(grid[i][j-1], grid[i-1][j]) + grid[i][j];
                }
                else if(i == 0 && j != 0){
                    grid[i][j] = grid[i][j-1] + grid[i][j];
                }
                else if(i != 0 && j == 0){
                    grid[i][j] = grid[i-1][j] + grid[i][j];
                }
            }
        }
        
        return grid[m-1][n-1];
    }
}

343. Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example:

given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note:

You may assume that n is not less than 2 and not larger than 58.

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private int max3(int x, int y, int z){
        return Math.max(x, Math.max(y, z));
    }
    
    private int breakHelper(int n){
        if(n == 1){
            return 1;
        }
        
        int res = 0;
        for(int i = 1; i < n; ++i){
            res = max3(res, i * (n-i), i * breakHelper(n-i));
        }
        
        return res;
    }
    
    public int integerBreak(int n) {
        return breakHelper(n);
    }
}

自顶向下的记忆化搜索

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
class Solution {
    private int[] memo;
    
    private int max3(int x, int y, int z){
        return Math.max(x, Math.max(y, z));
    }
    
    private int breakHelper(int n){
        if(n == 1){
            return 1;
        }
        
        if(memo[n] != 0){
            return memo[n];
        }
        
        int res = 0;
        for(int i = 1; i < n; ++i){
            //重叠的子问题 存在memo数组中了,
            //一旦break的元素发现已经被处理，直接取出来
            res = max3(res, i * (n-i), i * breakHelper(n-i));
        }
        
        memo[n] = res;
        
        return res;
    }
    
    public int integerBreak(int n) {
        memo = new int[n+1];
        
        return breakHelper(n);
    }
}

dp版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private int max3(int x, int y, int z){
        return Math.max(x, Math.max(y, z));
    }
    
    public int integerBreak(int n) {
        int []memo = new int[n+1];
            
        for(int i = 2; i <= n; ++i){
            for(int j = 1; j < i; ++j){
                //memo[i-j]相当于记忆化搜索时，进入子结构breakHelper()
                memo[i] = max3(memo[i], j * (i-j), j * memo[i-j]);
            }
        }
        
        return memo[n];
    }
}

279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

状态转移方程

1
2
3
4
5
6
//      0 1 2 3 4 5 6 7 8 9 10 11
//  1   0 1 2 3 4 5 6 7 8 9 10 11
//  4   0 0 0 0 1 2 3 4 2 3 4  5
//  9   0 0 0 0 0 0 0 0 0 1 2  3
F(i, c) = min{ F(i-1, c), F(i-1, c-v[i]) }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numSquares(int n) {
        int C = n;
        int []memo = new int[C+1];
        Arrays.fill(memo, Integer.MAX_VALUE);
        memo[0] = 0;
        for(int i = 1; i <= C; ++i){
            for(int j = 1; j * j<= i; ++j){
                memo[i] = Math.min(memo[i], 1 + memo[i-j*j]);
            }
        }
        return memo[C];
    }
}

91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

Given an encoded message containing digits, determine the total number of ways to decode it.

Example:

Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

解题思路:

自右往左

1
2

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

点击加载

解题思路:

对于第一行和第一列，每个元素的可到达路径只有1种
对于其他元素，每个元素可到达的路径都是由上和左两个元素的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int uniquePaths(int m, int n) {
        int [][]memo = new int[m][n];
        memo[0][0] = 1;
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(i != 0 && j != 0){
                    memo[i][j] = memo[i][j-1] + memo[i-1][j];
                }
                else{
                    memo[i][j] = 1;
                }
            }
        }
        return memo[m-1][n-1];
    }
}

63. Unique Paths II

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Example:

1
2
3
4
5
6
7
8
9
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.

解题思路:

若当前元素是1，会干扰到后续元素的判断，
因为它不知道这是障碍或者是路径1
所以开辟新空间给新数组

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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;        
        int [][]A = new int[m][n];
        
        if(obstacleGrid[0][0] == 1){
            return 0;
        }
        else{
            A[0][0] = 1;
        }
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(obstacleGrid[i][j] == 1){
                    A[i][j] = 0;
                }
                else if(i != 0 && j != 0){
                    A[i][j] = A[i-1][j] + A[i][j-1];
                }
                else if(i != 0){
                    A[i][j] = A[i-1][j];
                }
                else if(j != 0){
                    A[i][j] = A[i][j-1];
                }
            }
        }
        return A[m-1][n-1];
    }
}

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

解题思路:

1
2
状态转移函数	考虑偷取[x...n-1]范围里的房子
f(0) = max{ v(0) + f(2), v(1) + f(3), .... , v(n-3) + f(n-1), v(n-2), v(n-1) }

暴力搜索法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int tryRob(int []nums, int index){
        if(index >= nums.length){
            return 0;
        }
        
        int res = 0;
        for(int i = index; i < nums.length; ++i){
            res = Math.max(res, nums[i] + tryRob(nums, i+2));
        }
        
        return res;
    }
    
    public int rob(int[] nums) {
        
        return tryRob(nums, 0);
    }
}

记忆化搜索:

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
class Solution {
    
    private int[]memo;
    
    public int tryRob(int []nums, int index){
        if(index >= nums.length){
            return 0;
        }
        
        if(memo[index] != -1){
            return memo[index];
        }
        
        int res = 0;
        for(int i = index; i < nums.length; ++i){
            res = Math.max(res, nums[i] + tryRob(nums, i+2));
        }
        memo[index] = res;
        
        return res;
    }
    
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        memo = new int[nums.length];
        for(int i = 0; i < nums.length; ++i){
            memo[i] = -1;
        }
            
        return tryRob(nums, 0);
        
    }
}

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        
        int []memo = new int[n];
        memo[n-1] = nums[n-1];
        
        for(int i = n-2; i >= 0; --i){
            for(int j = i; j < n; ++j){
                memo[i] = Math.max(memo[i], nums[j] + (j+2 < n ? memo[j+2] : 0));
            }
        }
        
        return memo[0];
    }
}

121. Best Time to Buy and Sell Stock

Say you have an array for which the Ith element is the price of a given stock on day i.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.

状态转移方程

1
F(i) = max{ maxProfit, F(i+1)}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        for(int i = 0; i < prices.length; ++i){
            minPrice = Math.min(minPrice, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
        
        return maxProfit;
    }
}

0-1背包问题

有一个背包，它的容量为C(capacity)。现在有n种不同的物品，编号为0到n-1，其中每一个物品的重量为W(i)，价值为V(i)，问可以在这个背包中放哪些东西，使得在不超过C的基础上，物品的总价值最大。

1
2
3
F(n, C)考虑将n个物品放入容量为C的背包，使得价值最大
状态转移方程：
F(i, c) = max{ F(i-1, c), v(i) + F(i-1, c-w(i))}

Example:

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
//记忆化搜索
public class QKnapsack {
    private int [][]memo;
    //用[0 ... index]的物品, 填充容积为C的背包的最大价值
    //index 物品的编号  w[index] 物品的重量
    //                v[index] 物品的价值
    private int bestValue(int []w, int []v, int index, int c){
        if(index < 0 || c <= 0){
            return 0;
        }
        if(memo[index][c] != -1){
            return memo[index][c];
        }
        int res = bestValue(w, v, index-1, c);
        if(c >= w[index]){
            res = Math.max(res, v[index] + bestValue(w, v, index-1, c-w[index]));
        }
        memo[index][c] = res;
        return res;
    }
    public int knapsack01(int []w, int []v, int C){
        int n = w.length;
        memo = new int[n][C+1];
        for(int[] A : memo){
            for(int i = 0; i < A.length; ++i){
                A[i] = -1;
            }
        }
        return bestValue(w, v, n-1, C);
    }
}
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
//动态规划
    public int knapsack01_1(int []w, int []v, int C){
        assert (w.length == v.length);
        int n = w.length;
        if(n == 0){
            return 0;
        }
        
        int [][] memo = new int[n][C+1];
        for(int []A : memo){
            for(int i = 0; i < A.length; ++i){
                A[i] = -1;
            }
        }
        
        //编号0的物品, 尝试放入背包内
        for(int k = 0; k <= C; ++k){
            memo[0][k] = (k >= w[0]) ? v[0] : 0;
        }
        
        for(int i = 1; i < n; ++i){
            for(int j = 0; j <= C; ++j){
                memo[i][j] = memo[i-1][j];  //当前物品i不放入背包的情况
                //背包空间足够
                if(j >= w[i]){  
                    //memo[i-1][j-w[i]] 当存入物品i-1的时,并且空间只有j-w[i]的情况下
                    memo[i][j] = Math.max(memo[i][j], v[i]+memo[i-1][j-w[i]]);
                }
            }
        }
        
        return memo[n-1][C];
    }

dp优化

空间优化
第i行元素只依赖于第i-1行元素，理论上只需要保持两行元素
空间复杂度 O(2*C) = O(C)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int knapsack01_2(int []w, int v, int C){
     
    ...
    int [][] memo = new int[2][C+1];    //只创建两行背包
    ...
    for(int i = 1; i < n; ++i){
        for(int j = 0; j <= C; ++j){
            memo[i%2][j] = memo[(i-1)%2][j];  //当前物品i不放入背包的情况
            //背包空间足够
            if(j >= w[i]){
                //memo[i-1][j-w[i]] 当存入物品i-1的时,并且空间只有j-w[i]的情况下
                memo[i%2][j] = Math.max(memo[i%2][j], v[i]+memo[(i-1)%2][j-w[i]]);
            }
        }
    }
    
    return memo[(n-1)%2][C];
}

空间和时间的同时优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int knapsack01_3(int []w, int []v, int C){
    int n = w.length;
    
    int []memo = new int[C+1];
    for(int i = 0; i < memo.length; ++i){
        memo[i] = -1;
    }
    
    for(int k = 0; k <= C; ++k){
        memo[k] = (k >= w[0]) ? v[0] : 0;
    }
    
    for(int i = 1; i < n; ++i){
        for(int j = C; j >= w[i]; --j){
            //现在只有一行空间，memo索引考虑的是背包的容量
            memo[j] = Math.max(memo[j], v[i]+memo[j-w[i]]);
        }
    }
    
    return memo[C];
}

416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example:

1
2
3
4
5
6
7
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Note:

  • Each of the array element will not exceed 100.
  • The array size will not exceed 200.

解题思路:

F(n, C)考虑将n个物品填满容量为C的背包

1
2
3
F(i, c) = F(i-1, c) || F(i-1, c - w(i))
时间复杂度 O(n * sum/2) = 100 * 100*200/2 = 100万
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
//记忆化搜索
class Solution {
    //memo[index][c] 表示使用索引index为[0...index]的这些元素
    //是否可以完全填充一个容量为C的背包
    //-1表示未计算，0表示不可以，1表示可以
    private int [][]memo;
    
    //使用nums[0...index]，是否可以完全填充一个容量为c的背包
    private boolean tryPartition(int []nums, int index, int c){
        if(c == 0){
            return true;
        }
        
        if(index < 0 || c < 0){
            return false;
        }
        
        if(memo[index][c] != -1){
            return memo[index][c] == 1;
        }
        
        memo[index][c] = (tryPartition(nums, index-1, c) ||
                tryPartition(nums, index-1, c-nums[index])) ? 1 : 0;
        
        return memo[index][c] == 1;
    }
    
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int a : nums){
            sum += a;
        }
        
        if(sum % 2 == 1){
            return false;
        }
        
        int C = sum/2;
        int n = nums.length;
        memo = new int[n][C+1];
        for(int []A : memo){
            for(int i = 0; i < A.length; ++i){
                A[i] = -1;
            }
        }
        
        return tryPartition(nums, n-1, C);
    }
}
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
//动态规划
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int a : nums){
            sum += a;
        }
        
        if(sum % 2 == 1){
            return false;
        }
        
        int C = sum/2;
        int n = nums.length;
        boolean [][]memo = new boolean[n][C+1];
        for(int k = 0; k <= C; ++k){
            memo[0][k] = (k == nums[0]);    //当只有索引0元素的时候，背包容量为k的是否刚好被完全填充
        }
        
        for(int i = 1; i < n; ++i){
            for(int j = 0; j <= C; ++j){
                memo[i][j] = memo[i-1][j];  //索引i不加入背包 ---1
                //此时背包容量j足够填充nums[i]
                if(j >= nums[i]){
                    //当加入索引i,背包容量剩余j-nums[i]
                    //此时索引i-1在容量为j-nums[i]的情况下是否能够满足，与情况1取或运算
                    memo[i][j] = memo[i][j] || memo[i-1][j-nums[i]];
                }
            }
        }
        
        return memo[n-1][C];
    }
}

dp优化

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
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int a : nums){
            sum += a;
        }
        
        if(sum%2 == 1){
            return false;
        }
        int C = sum/2;
        int n = nums.length;
        boolean []memo = new boolean[C+1];
        for(int k = 0; k < memo.length; ++k){
            memo[k] = (k == nums[0]) ;
        }
        
        for(int i = 1; i < n; ++i){
            for(int j = C; j >= nums[i]; --j){
                memo[j] = memo[j] || memo[j-nums[i]];
            }
        }
        
        return memo[C];
    }
}

322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example:

1
2
3
4
5
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
coins = [2], amount = 3
return -1.

Note: 完全背包问题

1
You may assume that you have an infinite number of each kind of coin.

状态转移方程

1
F(i, c) = min{ F(i-1, c), F(i-1, c-v[1])+1, F(i-1, c-v[2])+1, ..., F(i-1, c-v[x])+1 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    
    public int coinChange(int[] coins, int amount) {
        int C = amount;
        int n = coins.length;
        int []memo = new int[C+1];
        Arrays.fill(memo, C+1);
        
        memo[0] = 0;
        
        for(int i = 1; i <= C; ++i){
            for(int j = 0; j < n; ++j){
                if(coins[j] <= i){
                    memo[i] = Math.min(memo[i], memo[i-coins[j]]+1);
                }
            }
        }
        
        return memo[C] > C ? -1 : memo[C];
    }
}

139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

Example:

1
2
3
4
5
given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

状态转移方程

1
F(i, s) = F(i-1, s-word) && F(i, word)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int C = s.length();
        boolean []memo = new boolean[C+1];
        memo[0] = true;
        for(int i = 1; i <= C; ++i){
            for(int j = 0; j < i; ++j){
                memo[i] = memo[j] && wordDict.contains(s.substring(j, i));
                if(memo[i]){
                    break;
                }
            }
        }
        
        return memo[C];
    }
}

377. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.

状态转移方程

1
F(i, c) = F(i-1) + F(c-v[i])
1
2
3
4
5
n\C - 1 2 3 4	1 2 3 4		1 2 3 4		1 2 3 4
------------------------------------------------------
1   - 1 0 0 0	1 1 0 0		1 1 1 0		1 1 1 1
2   - 0 0 0 0	0 2 0 0		0 2 3 0		0 2 3 5
3   - 0 0 0 0	0 0 0 0		0 0 4 0		0 0 4 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int C = target;
        int n = nums.length;
        int memo[] = new int[C+1];
        memo[0] = 1;
        for(int i = 1; i <= C; ++i){
            for(int j = 0; j < n; ++j){
                if(nums[j] <= i){
                    memo[i] += memo[i-nums[j]];
                }
            }
        }
        return memo[C];
    }
}

最长上升子序列

300. Longest Increasing Subsequence

LIS(i) 表示以第i个数字为结尾的最长上升子序列的长度
即[0, …, i]的范围内，选择数字nums[i]可以获得的最长上升子序列的长度

1
LIS(i) = max(1 + LIS(j) if(nums[i] > nums[j])), 任意i > j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLIS(int[] nums) {
        
        int n = nums.length;
        int []memo = new int[n];
        Arrays.fill(memo, 1);
        
        for(int i = 1; i < n; ++i){
            for(int j = 0; j < i; ++j){
                if(nums[i] > nums[j]){
                    memo[i] = Math.max(memo[i], memo[j]+1);
                }
            }
        }
        
        int res = 0;
        for(int i = 0; i < n; ++i){
            res = Math.max(res, memo[i]);
        }
        
        return res;
    }
}

300-1. Print LIS

376. Wiggle Subsequence

状态转移方程

1
2
3
4
5
i = j+1
if nums[i] > nums[j]:
	up = down +1
else nums[i] < nums[j]:
	down = up+1
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
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        
        int n = nums.length;
        int []up = new int[n];
        int []down = new int[n];
        
        up[0] = 1;
        down[0] = 1;
        
        for(int i = 1; i < n; ++i){
            if(nums[i-1] < nums[i]){
                up[i] = down[i-1] + 1;
                down[i] = down[i-1];
            }
            else if(nums[i-1] > nums[i]){
                up[i] = up[i-1];
                down[i] = up[i-1]+1;
            }
            else{
                up[i] = up[i-1];
                down[i] = down[i-1];
            }
        }
        
        return Math.max(up[n-1], down[n-1]);
    }
}

优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        
        int up = 1;
        int down = 1;
        for(int i = 1; i < nums.length; ++i){
            if(nums[i-1] < nums[i]){
                up = down+1;
            }
            else if(nums[i-1] > nums[i]){
                down = up + 1;
            }
        }
        
        return Math.max(down, up);
    }
}

最长公共子序列

(Lintcode)77. Longest Common Subsequence

状态转移方程

1
2
3
4
5
LCS(m,n ) S1[0 ... m]和S2[0 .. n ]的最长公共子序列
if S1[m] == S2[n]:
	LCS(m, n) = 1 + LCS(m-1, n-1);
else:
	LCS(m, n) = max{ LCS(m-1, n), LCS(m, n-1) }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int longestCommonSubsequence(String A, String B) {
    int m = A.length();
    int n = B.length();
    int [][]memo = new int[m+1][n+1];
    for(int i = 1; i <= m; ++i){
        for(int j = 1; j <= n; ++j){
            if(A.charAt(i-1) == B.charAt(j-1)){
                memo[i][j] = 1 + memo[i-1][j-1];
            }
            else{
                memo[i][j] = Math.max(memo[i-1][j], memo[i][j-1]);
            }
        }
    }
    return memo[m][n];
}