课程的最后一天，也是新年上班的第一天，感谢王老师的教育和陪伴，祝您生活开心，工作顺利。
今天的题目比前几天的都难一点，只做了三题，太累了TaT。对于动态规划和贪心总觉得很巧妙，如果想不到动态转移方程式，就很难做，但要是想到了，真的是豁然开朗。对于这一类题，还是要多锻炼，找动态转移方程式要从最后一个结果出发，去想这个结果可以由什么得到，知道之前所有结点的信息，如何推导出当前结点的信息，其实和高中学的归纳法有一点点像。
下面给出我今天做的三题的解题思路和代码
1.    Problem 121. Best Time to Buy and Sell Stock
解题思路：这道题很久以前做的，我们可以维持两个变量 - 分别对应于最小谷值和最大利润（销售价格和最低价格之间的最大差异）的minprice 和maxprofit。
代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/array/easy/Problem121.java
2.    Problem 120. Triangle
解题思路：这道题给一个由整数组成的三角形，自上而下寻找顶点到三角形边的最短的一条路径，设置一个数组A[0...n-1][0...n-1]，A[i][j]代表到达第i行第j列结点的最短路径
* DP转移方程式为：A[i][j]=min(A[i-1][j-1],A[i-1][j])+triangle[i][j]
* 其中二维数组可以简化为一维数组，因为我们只需要上一行结点的信息
* 然后遍历到达最后一行的节点的路径，找到最短路径的值
代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/dp/Problem120_Triangle.java
3.    Problem 322. Coin Change
解题思路：这道题是给定具有n个不同金额的硬币（硬币个数无限）coins[0...n-1]，给一个整数amount，是否给的硬币能正好达到整数，给出能组成整数最少需要的硬币个数.
解法是设置一个数组A[0...amount],进行初始化A[0]=0;A[1...amount] = -1;保存的是当给定金额为i时，所需要的最少的硬币。
* dp转移方程式为 A[k] = 1+min(A[k-coins[0]],A[k-coins[1]],....A[k-coins[n-1]]).
* 这里要注意的是判断A[k]是否有解
代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/dp/Problem322_CoinChange.java
课程完结撒花，真的学到好多，自己以后还会反复回顾的，再次感谢王争老师，还有每天负责朗读的声音好好听的修阳小哥哥。

8皇后问题

public class EightQueen {

    private static final int QUEEN_NUMBER = 8; // 皇后个数
    private int[] columns = new int[QUEEN_NUMBER]; // 每个皇后存储的列 (row, col), row天然不相等
    private int total = 0;

    public int solution() {
        queen(0);
        return total;
    }

    private void queen(int row) {
        if (row == QUEEN_NUMBER) {
            total++;
        } else {
            for (int col = 0; col != QUEEN_NUMBER; col++) {
                columns[row] = col;
                if (isPut(row)) {
                    queen(row+1);
                }
            }
        }
    }

    private boolean isPut(int row) {
         for (int i = 0; i != row; i++) {
             if (columns[row] == columns[i] || row - i == Math.abs(columns[row]-columns[i])) {
                 return false;
             }
         }
         return true;
    }

}

老师留的题都很不错，正在刷之前没做过的LeetCode题。
参与下答对三题送课程的活动:
Day 1：
1.求众数(Python)
class Solution:
    def majorityElement(self, nums):
        return sorted(nums)[len(nums) // 2]
2.缺失的第一个正数(Golang)
func firstMissingPositive(nums []int) int {
    if len(nums) == 0 {
        return 1
    }

    var arr = make([]bool, len(nums)+1)
    var idx = 1
    for i := 0; i < len(nums); i++ {
        if nums[i] >= 0 && nums[i] < len(arr) {
            arr[nums[i]] = true
        }
    }

    for i := 1; i < len(arr); i++ {
        if arr[i] == false {
            idx = i
            break
        } else {
            idx = i + 1
        }
    }

    return idx
}
Day 7:
3. 买卖股票的最佳时机(Python)
class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0
        min_price = prices[0]
        res = 0
        for i in prices[1:]:
            min_price = min(min_price, i)
            if res < i - min_price:
                res = i - min_price
        return res

买卖股票的最佳时机 go 语言实现
package main

import "fmt"

func maxProfit(prices []int) int {
    max := -1
    for i := 0; i < len(prices); i++ {
        for j := i + 1; j < len(prices); j++ {
            profit := prices[j] - prices[i]
            if profit > 0 && profit > max {
                max = profit
            }
        }
    }

    if max == -1 {
        return 0
    }

    return max
}

func main() {
    testData1 := []int{7, 1, 5, 3, 6, 4}
    testData2 := []int{7, 6, 4, 3, 1}

    fmt.Println(maxProfit(testData1))
    fmt.Println(maxProfit(testData2))
}

零钱兑换 - GO

func coinChange(coins []int, amount int) int {
    var dp []int = make([]int, amount+1)
    for _, record := range coins {
        if amount >= record {
            dp[record] = 1
        }
    }

    for i := 1; i <= amount; i++ {
        dp[i] = amount + 1
        for _, record := range coins {
            if i-record >= 0 {
                dp[i] = min(dp[i-record]+1, dp[i])
            }
        }
    }

    if dp[amount] > amount {
        return -1
    }

    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

买卖股票的最佳时机 go 语言实现

func maxProfit(prices []int) int {

    max:=0
    for i:=0;i<len(prices);i++{
        for j:=0;j<i;j++{
            num:=prices[i]-prices[j]
            if num>max{
                max=num
            }
        }
    }
    return max
}

零钱兑换 go语言实现
func coinChange(coins []int, amount int) int {
    if amount==0{
        return 0
    }
    if len(coins)==0 && amount!=0{
        return -1
    }

    isSmall:=true
    for _,coin:=range coins{
        if coin<=amount{
            isSmall=false
        }
    }
    if isSmall{
        return -1
    }
    grid:=make([]int,amount+1)


    for _,coin:=range coins{
        if coin<=amount{
            grid[coin]=1
        }
        if coin==amount{
            return 1
        }
    }
    for i:=2;i<amount+1;i++{
        newGrid:=make([]int,amount+1)
        for j:=1;j<amount+1;j++{
            for _,coin:=range coins{
                if grid[j]==1 && j+coin<=amount{
                    newGrid[j]=1
                    newGrid[j+coin]=1
                }
            }
        }
        grid=newGrid
        if grid[amount]==1{
            return i
        }
    }
    return -1
}

最小路径和 go实现

func minPathSum(grid [][]int) int {
    l:=len(grid)
    w:=len(grid[0])
    sum:=make([][]int,l)
    for i:=0;i<l;i++{
        sum[i]=make([]int,w)
    }
    sum[0][0]=grid[0][0]
    for i:=1;i<w;i++{
        sum[0][i]=grid[0][i]+sum[0][i-1]
    }
    for j:=1;j<l;j++{
        sum[j][0]=grid[j][0]+sum[j-1][0]
    }
    for i:=1;i<l;i++{
        for j:=1;j<w;j++{
            sum[i][j]=less(sum[i-1][j],sum[i][j-1])+grid[i][j]
        }
    }

    return sum[l-1][w-1]
}

func less(i,j int) int{
    if i>j{
        return j
    }else{
        return i
    }
}

正则表达式匹配 go语言实现，还是看别人的提示搞出来的
func isMatch(s string, p string) bool {
    if len(p)==0{
        if len(s)==0{
            return true
        }else{
            return false
        }
    }
    if len(p)==1{
        if len(s)==1 && (s[0]==p[0] || p[0]=='.'){
            return true
        } else {
            return false
        }
    }
    if p[1]!='*'{
        if len(s)==0{
            return false
        }
        return (s[0]==p[0]||p[0]=='.') && isMatch(s[1:],p[1:])
    }else{
        for ;len(s)!=0 && (s[0]==p[0]||p[0]=='.');{
            if isMatch(s,p[2:]){
                return true
            }
            s=s[1:]
        }
        return isMatch(s,p[2:])
    }



    return true
}

//零钱兑换
#include<iostream>
#include<algorithm>
using namespace std;
int coins[10];
int amount;
int k;//k代表纸币的数目
int dp[20];//代表面值最大，也可以采用动态扩容的方式
int cmax = 32767;
int coinChange(int coins[],int amount){
    for(int i = 1;i <= amount;i++){
        dp[i] = cmax;
        for(int j = 0;j < k;j++){
            int t = coins[j];
            if(i >= t && coins[i - t] != cmax){
                dp[i] = min(dp[i - t] + 1,dp[i]);
            }
        }
    }
    if(dp[amount] < cmax && dp[amount] > 0){
        return dp[amount];
    }
    else
        return -1;
}
int main(){
    k = 0;
    while(true){
        cin>>k;
        for(int i = 0;i < k;i++){
            cin>>coins[i];
        }
        cin>>amount;
        cout<<coinChange(coins,amount)<<endl;
    }    
}

回溯0-1背包问题
#include<iostream>
using namespace std;
int v[10] = {2,2,4,6,3};
int M;//代表背包的容积
int n;
int cmax = 0;

void f(int w,int k){
//    if(w == 0){
//        if(w > max) max = w;
//    }
    if(w == M || k == n){
        if(w > cmax) cmax = w;
        return ;
    }
    f(w,k + 1);
    if(w + v[k] <= M){
        f(w + v[k],k + 1);
    }
}
int main(){
    //v[] = {2,2,4,6,3};
    M = 9;
    n = 5;
    f(0,0);
    cout<<cmax<<endl;
}