動态規劃1

1.計數

2.最大最小值

3.存在性

1.确定狀态：确定最優政策最後一步，确定子問題

2.轉移方程：根據子問題

3.初始條件和邊界情況

4.計算順序：利用之前的計算結果

常見動态規劃類型：

1.坐标型 2.序列型 3.劃分型 4.區間型 5.背包型 6.最長序列 7.博弈性 8.綜合型

669. Coin Change

思路：屬于求最值情況

https://www.lintcode.com/problem/coin-change/description?_from=ladder&&fromId=16

public class Solution {
    /**
     * @param coins: a list of integer
     * @param amount: a total amount of money amount
     * @return: the fewest number of coins that you need to make up
     */
    public int coinChange(int[] coins, int amount) {
        // write your code here
        if(coins==null || coins.length ==0){
            return 0;
        }
        
        int[] f = new int[amount+1];
        
        f[0]=0;
        
        //從i=1開始疊代，從0開始疊代是錯誤的
        for(int i=1;i<=amount;i++){
            f[i] = Integer.MAX_VALUE;
            for(int j =0;j<coins.length;j++){
                if(i>=coins[j] && f[i-coins[j]]!=Integer.MAX_VALUE){
                    f[i] = Math.min(f[i],f[i-coins[j]]+1);
                }
            }
        }
        
        if(f[amount]==Integer.MAX_VALUE){
            return -1;
        }
        
        return f[amount];
    }
}      

View Code

191. Maximum Product Subarray

思路：因為有負數的情況，需要兩個狀态方程分别記錄過程中的最大值，最小值

https://www.lintcode.com/problem/maximum-product-subarray/description?_from=ladder&&fromId=16

public class Solution {
    /**
     * @param nums: An array of integers
     * @return: An integer
     */
    public int maxProduct(int[] nums) {
        // write your code here
        int[] f = new int[nums.length];
        int[] g = new int[nums.length];
        
        f[0] = nums[0];  //最大值
        g[0] = nums[0]; //最小值
        int max = Integer.MIN_VALUE;
        
        for(int i=1;i<nums.length;i++){
            f[i]=Math.max(nums[i],Math.max(f[i-1]*nums[i],g[i-1]*nums[i]));
            g[i]=Math.min(nums[i],Math.min(f[i-1]*nums[i],g[i-1]*nums[i]));
        }
        
        for(int i=0;i<nums.length;i++){
            max = Math.max(f[i],max);
        }
        
        return max;
    }
}      

View Code

轉載于:https://www.cnblogs.com/lizzyluvcoding/p/10795551.html