狂暴复习之路20160610 Dynamic Programming I

338	Counting Bits

public int[] countBits(int num) {
    int[] result = new int[num+1];
    result[0] = 0;
    if (num!=0)
    {
        int flag = 0;
        for (int i =1; i<=num;i++)
        {
            result[i] = result[flag]+1;
            flag++;
            if (flag+1>num||result[flag+1]==0)
                flag=0;
            else                flag++;
        }
    }
    return result;
}

没啥好说的从头到尾扫描

343
Integer Break

public int integerBreak(int n) {
    if (n == 2)
        return 1;
    if (n == 3)
        return 2;
    return (int)Math.pow(3, (n-2)/3)*((n-2)%3+2);
}
这道题的名字叫做 凑3.


96
Unique Binary Search Trees


public int numTrees(int n) {
    int[] resultSet = new int[n+1];
    resultSet[0] = 1;
    resultSet[1] = 1;
    if (n<2)
        return resultSet[n];
    for (int i = 2; i <n ; i++) {
        int temp = 0;
        for (int j = 0; j <i ; j++) {
            temp += resultSet[j]*resultSet[i-1-j];
        }
        resultSet[i] = temp;
    }
    return resultSet[n];
}
最优子结构 Σ（根节点*左子树的个数*右子树的个数）

312
Burst Balloons


public int DP (int l,int r,int[] nums,int[][] dp)
{
    if (dp[l][r] > 0)
        return dp[l][r];
    for (int x = l; x <= r; x++) {
        dp[l][r] = Math.max(dp[l][r], DP(l, x - 1, nums, dp) + nums[l - 1] * nums[x] * nums[r + 1] + 
DP(x + 1, r, nums, dp));
    }
    return dp[l][r];
}
public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] temp = new int[n + 2];
    
    for (int i = 0; i < n; i++) 
        temp[i + 1] = nums[i];
    
    temp[0] = temp[n + 1] = 1;
    int[][] dp = new int[n + 2][n + 2];
    return DP(1, n, temp, dp);
}
从只剩1个气球开始想 最优子结构 dp[l][r] = Math.max(dp[l][r], DP(l, x - 1, nums, dp) + nums[l - 1] * nums[x] * 
nums[r + 1] + DP(x + 1, r, nums, dp));

309
Best Time to Buy and Sell Stock with Cooldown


public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0)
        return 0;
    int len = prices.length;
    int[] sell = new int[len];
    int[] coolDown = new int[len];
    sell[0] = 0;
    coolDown[0] = 0;
    for (int i = 1; i < len; i++) {
        sell[i] = Integer.max(sell[i - 1] + prices[i] - prices[i - 1], coolDown[i - 1]);
        coolDown[i] = Integer.max(sell[i - 1], coolDown[i - 1]);
    }
    return Integer.max(sell[len - 1], coolDown[len - 1]);
}
最优子结构 Max= max（sell,coolDown）,sell[i] = Integer.max(sell[i - 1] + prices[i] - prices[i - 1],
 coolDown[i - 1]);
coolDown[i] = Integer.max(sell[i - 1], coolDown[i - 1]);


70
Climbing Stairs


public int climbStairs(int n) {
    if (n==0)
        return 0;
    if (n==1)
        return 1;
    if (n==2)
        return 2;
    int[] resultSet = new int[n+1];
    resultSet[0] = 0;
    resultSet[1] = 1;
    resultSet[2] = 2;
    for (int i =3; i<=n;i++)
    {
        resultSet[i] = resultSet[i-1]+resultSet[i-2];
    }
    return resultSet[n];
}
没啥可说的，resultSet[i] = resultSet[i-1]+resultSet[i-2];

53
Maximum Subarray


参见Array I

62
Unique Paths




public int uniquePaths(int m, int n) {
    if (m==0&&n==0)
        return 0;
    if (m==1&&n==1)
        return 1;
    int[][] resultSet = new int[m][n];
    for (int i = 0; i <m ; i++) {
        resultSet[i][0] = 1;
    }
    for (int i = 0; i <n ; i++) {
        resultSet[0][i] = 1;
    }
    for (int i = 1; i <m ; i++) {
        for (int j = 1; j <n ; j++) {
            resultSet[i][j] = resultSet[i-1][j] + resultSet[i][j-1];
        }
    }
    return resultSet[m-1][n-1];
}
最优子结构 resultSet[i][j] = resultSet[i-1][j] + resultSet[i][j-1];



121
Best Time to Buy and Sell Stock


参见Array I



64
Minimum Path Sum


public int minPathSum(int[][] grid) {
    int height = grid.length;
    int width = grid[0].length;
    for (int i = 0; i< height; i++)
        for (int j = 0; j<width ; j ++)
        {
            if (i==0&&j==0) {
                continue;
            }
            else if(i==0) {
                grid[i][j] += grid[i][j-1];
            }
            else if(j==0) {
                grid[i][j] += grid[i-1][j];
            }
            else {
                grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
            }
        }
    return grid[height-1][width-1];
}
从左到右，从上到下，选最小值叠加grid[i][j]=(grid[i][j]+Math.min(grid[i-1][j],grid[i][j-1]));