社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
动态规划一般是来解决
这么一说,太抽象了,这四部曲是什么鬼东西(黑人问号.jpg)???接下来先用例子分析分析
问题:(lintcode:669)
首先,看到这种题,先不考虑算法,直接凭直觉的想法是这样的
7元*3+5元*1+2元*1=28 (呃,好像不能这样),再这样
7元*3+2元*3=27 ,一共6枚硬币(这样总可以了吧)
其实,正确答案是7元*1+5元*4=27 ,5枚硬币(震惊!!!!!!)
接下来用动态规划来(四部曲)分析:
首先我们把最后一个硬币的面值是ak,那么前面的硬币值肯定是27-ak
接下下,"最后一步"还有两个注意的关键点
还有个问题,我们还不知ak是多少,所以需要
这样我们的第一步就完成了
根据第一步的状态,我们这样设置,(注意,上面的大括号在这一步已经变成方括号了)
完成这一步可以先喝杯咖啡了
首先我们的硬币肯定从f[0]即凑出0元需要0枚硬币,
接下来是边界问题:
有了我们前面分析的前三步,接下来就是计算顺序了,其实就是从f[0]开始计算而已,并把他们都记录下来
结果其实是这样的
/**
*
* @param {Array} coin 代表硬币的种类 [2,5,7]
* @param {int} M 代表拼凑的值 27
*/
function coinChange(coin, M) {
let f = []
f[0] = 0 //初始化第一步
for (let i = 1; i <= M; i++) {
f[i] = Number.MAX_VALUE //开始默认无穷大,即不能拼凑
for (let j = 0; j < coin.length; j++) { //这里右三种面值的硬币,需要循环一次
if (i - coin[j] >= 0 && f[i - coin[j]] != Number.MAX_VALUE) {//小于0即不能拼凑,和无穷大+1会报错
f[i] = Math.min(f[i], f[i - coin[j]] + 1)
}
}
}
if (f[M] == Number.MAX_VALUE) {
return -1
}
return f[M] //数组最后一个值就是我们想要的结果
}
/**
*
* @param {int} m m行
* @param {int} n n列
*/
/**
* @param m: positive integer (1 <= m <= 100)
* @param n: positive integer (1 <= n <= 100)
* @return: An integer
*/
const uniquePaths = function (m, n) {
let f=[];//先声明一个一维数组的
for(let i=0;i<m;++i){
f[i]=[];//声明二维数组的,其他语言有其他的写法
for(let j=0;j<n;++j){
if(i===0||j===0){
f[i][j]=1;
}else{
f[i][j]=f[i-1][j]+f[i][j-1];
}
}
}
console.log(f)
return f[m-1][n-1];
};
/**
*
* @param {Array} a //代表每个石头能跳的长度
*/
function canJump(a){
let n=a.length //数组的长度为能跳的总石头数
let f=[]
f[0]=true
for(let j=1;j<n;j++){
f[j]=false
for(let i=0;i<j;i++){
if(f[i]&&a[i]+i>=j){
f[j]=true
break
}
}
}
return f[n-1]
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!