动态规划是一种将复杂问题分解成更小的相互依赖的子问题来解决的优化技术
关键点:创建dp数组
1. 最小路径和
//给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
// 说明：每次只能向下或者向右移动一步。
// 示例:
// 输入:
// [
// [1,3,1],
// [1,5,1],
// [4,2,1]
// ]
// 输出: 7
// 解释: 因为路径 1→3→1→1→1 的总和最小。
//难度:中等
//解题思想:拆分成小问题算出到达每个子位置的最小路径和
var minPathSum = function (grid) {
var m = grid.length;
var n = grid[0].length;
var dp = Array.from({ length: grid.length }, item => item = []);
for (var i = 0; i < m; i++) {
for (var j = 0; j < n; j++) {
if (i === 0 && j === 0) {
dp[i][j] = grid[i][j]
} else if (i === 0 && j !== 0) {
dp[i][j] = grid[i][j] + dp[i][j - 1]
} else if (i !== 0 && j === 0) {
dp[i][j] = grid[i][j] + dp[i - 1][j]
} else {
dp[i][j] = Math.min(grid[i][j] + dp[i][j - 1], grid[i][j] + dp[i - 1][j])
}
}
}
return dp[m - 1][n - 1]
};
2.打家劫舍
// 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
// 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
// 示例 1:
// 输入: [1,2,3,1]
// 输出: 4
// 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
// 偷窃到的最高金额 = 1 + 3 = 4 。
//难度:中等
//解题思想: 根据3次以内的情况得到计算方程
var rob = function (nums) {
if (nums.length === 0) return 0;
//dp dynamic programming 动态规划简写
var dp = [];
dp[0] = 0;
dp[1] = nums[0];
for (var i = 2; i <= nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp.pop();
};
3.乘积最大子序列
// 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
// 示例 1:
// 输入: [2,3,-2,4]
// 输出: 6
// 解释: 子数组 [2,3] 有最大乘积 6。
// 示例 2:
// 输入: [-2,0,-1]
// 输出: 0
// 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
var maxProduct = function (nums) {
if (nums.length === 0) return 0;
//1.设置初始默认最大值,及默认乘积最大值,因为涉及负数最小值,当遇到负数时,最大和最小会互换,所以设置保存最小乘积变量.
let max = nums[0], imax = 1, imin = 1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] < 0) [imax, imin] = [imin, imax];
imax = Math.max(imax * nums[i], nums[i]);
imin = Math.min(imin * nums[i], nums[i]);
max = max > imax ? max : imax;
}
return max;
};
4. 最少硬币找零
//给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
// 示例 1:
// 输入: coins = [1, 2, 5], amount = 11
// 输出: 3
// 解释: 11 = 5 + 5 + 1
// 示例 2:
// 输入: coins = [2], amount = 3
// 输出: -1
//解题思路:所要金额可用amount减去coins中任一面值+1得到
//例如amount = 15,coins=[1,2,11,15],可由f(amount-coin)+1得到,即f(0)+1,f(4)+1,f(13)+1,f(14)+1
var coinsChange = function(amount,coins){
let dp = Array.from({length: amount+1},item=>item=Infinity);
dp[0] = 0;
for(var i=1;i<=amount;i++){
for(var coin of coins){
console.log(dp)
if(i-coin>=0){
//i=1时,dp[1]=dp[0]+1=1
dp[i] = Math.min(dp[i],dp[i-coin]+1)
}
}
}
return dp[amount]===Infinity?-1:dp[amount]
}
console.log(coinsChange(16,[1,2,5]))
5. 最长公共子序列
// 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
// 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
// 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
// 若这两个字符串没有公共子序列，则返回 0。
// 示例 1:
// 输入：text1 = "abcde", text2 = "ace"
// 输出：3
// 解释：最长公共子序列是 "ace"，它的长度为 3。
// 示例 2:
// 输入：text1 = "abc", text2 = "abc"
// 输出：3
// 解释：最长公共子序列是 "abc"，它的长度为 3。
// 示例 3:
// 输入：text1 = "abc", text2 = "def"
// 输出：0
// 解释：两个字符串没有公共子序列，返回 0
解题思路:列出一个二维dy数组,列出每个位置子序列长度
var longestCommonSubsequence = function (text1, text2) {
var m = text1.length,//rows
n = text2.length, //cols
dp = Array.from({ length: n + 1 }, item => item = new Array(m + 1).fill(-Infinity));
dp[0][0] = 0;
for (var i = 0; i <= n; i++) {
for (var j = 0; j <= m; j++) {
if (i === 0 || j === 0) {//有一方为0结论为0
dp[i][j] = 0
} else if (text1[j-1] === text2[i-1]) {//i,j对应字符相等
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
};
网友评论