// 这里我得说一下 在做动态规划的时候,我犯了一个巨大的错误,我想着用对象来代替数组存储,对象的下标为二维数组的下标,计算会出现问题
// 1.动态规划:利用历史记录避免进行重复计算,历史记录一般使用一维数组或者二维数组来保存
// 定义数组的含义:dp[i]是代表什么意思
// 找出数组元素之间的关系式:利用历史数据推出新的元素值
// 找出初始值
// 1.一只青蛙一次可以跳1级台阶或者2级台阶,求该青蛙跳上n级台阶共有多少种跳法
// 根据问题定义dp[i]:跳上i级台阶一共有dp[i]种跳法 =》 dp[n] = dp[n-2] + dp[n-1]
function stepsMethods(n) {
if(n=== 0) return 1
let nums = []
nums[1] = 1
nums[2] = 2
for(let i = 3; i <= n; i++) {
nums[i] = (nums[i-1] + nums[i-2])% 1000000007
}
return nums[n]
}
console.log(stepsMethods(4))
// 2.二维数组的dp: 一个机器人位于一个 m * n的网格左上角(终点在网格的右下角),机器人每次只能向下或者向右移动一步,
// 机器人每次只能向下或者向右移动一步,请问有多少条路径
// 根据问题定义dp[i][j]:当机器人从左上角走到(i,j)一共有dp[i][j]种路径;dp[i][j] = dp[i][j-1] + dp[i-1][j]
function juzhenMethods(m, n) {
const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
f[i][0] = 1;
}
for (let j = 0; j < n; j++) {
f[0][j] = 1;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
console.log(juzhenMethods(13,23))
// 3.给定一个包含非负整数的m * n网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和最小
// 举例:
// 输入:
// arr = [
// [1,3,1],
// [1,5,1],
// [4,2,1]
// ]
// 输出: 7
// 解释: 因为路径 1→3→1→1→1 的总和最小
// 定义dp[i][j] = m:到ij格子最小的值位m 则dp[i][j] = min(dp[i][j-1],dp[j-1][i])
function minJuzhenMethods(arr) {
let a = new Array(arr.length).fill(0).map(()=> new Array(arr[0].length).fill(0))
for(let i = 0; i < arr.length; i++) {
for(let j = 0; j < arr[i].length; j++) {
a[i][j] = arr[i][j]
}
}
for(let i = 0; i < arr.length; i++) {
for(let j = 0; j < arr[i].length; j++) {
if(i === 0 && j === 0) {
continue
}else {
// 要考虑边界情况,边界的值只能来源于他的左方或者上方
if(i === 0) {
a[i][j] = a[i][j-1] + a[i][j]
continue
}
if(j === 0) {
a[i][j] = a[i-1][j] + a[i][j]
continue
}
a[i][j] = Math.min(a[i-1][j],a[i][j-1]) + a[i][j]
}
}
}
return a[arr.length-1][arr[0].length-1]
}
let arr = [
[5,0,1,1,2,1,0,1,3,6,3,0,7,3,3,3,1],
[1,4,1,8,5,5,5,6,8,7,0,4,3,9,9,6,0],
[2,8,3,3,1,6,1,4,9,0,9,2,3,3,3,8,4],
[3,5,1,9,3,0,8,3,4,3,4,6,9,6,8,9,9],
[3,0,7,4,6,6,4,6,8,8,9,3,8,3,9,3,4],
[8,8,6,8,3,3,1,7,9,3,3,9,2,4,3,5,1],
[7,1,0,4,7,8,4,6,4,2,1,3,7,8,3,5,4],
[3,0,9,6,7,8,9,2,0,4,6,3,9,7,2,0,7],
[8,0,8,2,6,4,4,0,9,3,8,4,0,4,7,0,4],
[3,7,4,5,9,4,9,7,9,8,7,4,0,4,2,0,4],
[5,9,0,1,9,1,5,9,5,5,3,4,6,9,8,5,6],
[5,7,2,4,4,4,2,1,8,4,8,0,5,4,7,4,7],
[9,5,8,6,4,4,3,9,8,1,1,8,7,7,3,6,9],
[7,2,3,1,6,3,6,6,6,3,2,3,9,9,4,4,8]]
console.log(minJuzhenMethods(arr))
动态规划
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 首先我们来看 LeetCode 第 343 题,其实动态规划也包含了暴力求解,只不过我们按照一定规律,并且是在假设...
- 例1:LeetCode 第 70 题:Climbing Stairs 传送门:英文网址:70. Climbing ...
- 动态规划基本思想 动态规划的工作原理是先解决子问题,再逐步解决大问题。 用动态规划解决旅游规划问题 目前面对的问题...
- 基本认识 动态规划( dynamic programming )算法是解决多阶段决策过程最优化问题的一种常用方法,...