Fork me on GitHub

Three similiar questions about dynamic programming

Posted on

Linkage

https://leetcode.com/problems/coin-change/description/

https://leetcode.com/problems/unique-paths/description/

https://leetcode.com/problems/word-break/description/

Code

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

Pay attention to the non-result case, once we found the amount i is unavailable, we should mark it with MAX, otherwise the min function will be executed wrongly. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int coinChange(int[] coins, int amount) {
        int [] ret = new int[amount+1];
        ret[0] = 0;
        for(int i = 1; i <= amount; i++) {
            int min_count = 100000;
            for (int coin : coins){
                if(coin > i) continue;
                min_count = Math.min(min_count, ret[i-coin] + 1);
            }
            ret[i] = min_count;
        }
        if (ret[amount] >= 100000)
            return -1;
        
        return ret[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] ret = new boolean[s.length()+1];
        if (wordDict.size() == 0 || s.length() == 0) return false;
        
        ret[0] = true;
        for (int i = 1; i < s.length()+1; i++) {
            ret[i] = false;
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i < wordLength) continue;
                if (s.substring(i - wordLength, i).equals(word) && ret[i - wordLength] == true) 
                    ret[i] = true;
            }
        }
        
        
        return ret[s.length()];
    }
}