暴力递归到动态规划（五）

练习1(样本对应模型)

给定3个参数,N, M, K，怪兽有N滴血,等着英雄来砍自己，英雄每一次打击,都会让怪兽流失[0-M]的血量，到底流失多少?每一次在[0-M]上等概率的获得一个值，求K次打击之后,英雄把怪兽砍死的概率

练习2

arr是面值数组,其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值,且认为张数是无限的。返回组成aim的最少货币数

斜率优化（观察当前位置和附近位置的依赖关系）

练习3

给定一个正数1,裂开的方法有一种,(1)给定一个正数2,裂开的方法有两种,(1和1)、(2)给定一个正数3,裂开的方法有三种,(1、1、1)、(1、2)、(3)给定一个正数4,裂开的方法有五种,(1、1、1、1)、(1、1、2)、(1、 3)、(2. 2)、(4)给定一个正数n,求裂开的方法数（后面的数必须大于等于前面的数）。动态规划优化状态依赖的技巧

function process1(pre, rest) {
    if(rest==0)return 1
    if (pre > rest) {
        return 0
    }
   
    let ways = 0;
    for (let i = pre; i <= rest; i++) {
        ways += process1(i, rest - i)
    }
    return ways
}

function process(rest,num){
    if(rest==0)return 1
    if (num > rest) {
        return 0
    }
    let res = 0;          
    for (let zhang = 0; zhang*num <=rest; zhang++) {
        res+= process(rest-zhang*num,num+1)
    }
    return res
}