算法设计与技巧

• 分而治之算法
• 动态规划
• 贪心算法
• 回溯算法
• 著名算法问题

分而治之是算法设计的一种方法。它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将解决方式合并以解决原来的问题。

分而治之版本的二分搜索算法。

function binarySearchRecursive(arr,val,low,high){
    if(low <= high){
        const mid = Math.floor((low + high) / 2)
        const element = arr[mid]
        if(element < val){
            binarySearchRecursive(arr,val,mid + 1,high)
        }else if(element > val){
            binarySearchRecursive(arr,val,low,mid - 1)
        }else{
            return mid
        }
    }
}
function binarySearch(arr,val){
    const sortArr = quickSort(arr)
    const low = 0,high = arr.length - 1;
    return binarySearchRecursive(sortArr,val,low,high)

}

动态规划是一种将复杂问题分解成更小的子问题来解决的优化技术。

function minCoinChange(coins,amount){
    const cache = []
    function makeChange(value){
        if(!value){
            return []
        }
        if(cache[value]){
            return cache[value]
        }
        let min = []
        let newMin;
        let newAmount;
        for(let i = 0;i < coins.length;i++){
            let coin = coins[i]
            newAmount = value - coin
            if(newAmount >= 0){
                newMin = makeChange(newAmount)
            }
            if(newAmount >= 0 && (newMin.length < min.length -1 || !min.length) && (newMin.length || !newAmount)){
                min = [coin].concat(newMin)
            }
        }
        return (cache[value] = min)
    }
    return makeChange(amount)
}

　　

未完待续...