算法| ss 动态规划dp

2024-04-08 03:36

文章标签 算法动态规划 dp ss

本文主要是介绍算法| ss 动态规划dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

221.最大正方形
1143.最长公共子序列—1
70.爬楼梯
63.不同路径2
64.最小路径和

221.最大正方形

/*** @param {character[][]} matrix* @return {number}*/
// 思路
// dp初始化
// dp[i][j] 含义： 左 上  左上取 最小值  最后再加1
var maximalSquare = function (matrix) {const m = matrix.length;const n = matrix[0].length;const dp = Array(m).fill(0).map(() => Array(n).fill(0));let maxLen = 0;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (matrix[i][j] === "1") {if (i === 0 || j == 0) {dp[i][j] = 1;} else {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;}maxLen = Math.max(maxLen, dp[i][j]);}}}//   console.log(maxLen * maxLen);return maxLen * maxLen;
};maximalSquare([["1", "0", "1", "0", "0"],["1", "0", "1", "1", "1"],["1", "1", "1", "1", "1"],["1", "0", "0", "1", "0"],
]);

1143.最长公共子序列—1

/*** @param {string} text1* @param {string} text2* @return {number}*/
// 思路
// 构建dp 好像字符串比较是否相同 都是m+1 n+1 ，多一个，
// 双for循环时 s1取在第一个for之后取值 s2在第二个for里取值 ，都取前一个i-1 或者j-1
// dp[i][j]取值：相等时取左上角  不相等时取左或者上的最大值
// 返回结果
var longestCommonSubsequence = function (text1, text2) {const m = text1.length;const n = text2.length;const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));for (let i = 1; i <= m; i++) {const s1 = text1[i - 1];for (let j = 1; j <= n; j++) {const s2 = text2[j - 1];if (s1 === s2) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}//   console.table(dp);return dp[m][n];
};longestCommonSubsequence("abcde", "ace");
// ┌─────────┬───┬───┬───┬───┐
// │ (index) │ 0 │ 1 │ 2 │ 3 │
// ├─────────┼───┼───┼───┼───┤
// │    0    │ 0 │ 0 │ 0 │ 0 │
// │    1    │ 0 │ 1 │ 1 │ 1 │
// │    2    │ 0 │ 1 │ 1 │ 1 │
// │    3    │ 0 │ 1 │ 2 │ 2 │
// │    4    │ 0 │ 1 │ 2 │ 2 │
// │    5    │ 0 │ 1 │ 2 │ 3 │
// └─────────┴───┴───┴───┴───┘

70.爬楼梯

/*** @param {number} n* @return {number}*/
// 思路
// dp思路
// dp[i] 为跳n层台阶的方式
// 初始化 0 1 都只有1种方式
// 递推方式： 前面2种方式的和
var climbStairs = function (n) {const dp = [];dp[0] = 1;dp[1] = 1;for (let i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}console.log(dp[n]);return dp[n];
};
climbStairs(2);
climbStairs(10);

63.不同路径2

/*** @param {number[][]} obstacleGrid* @return {number}*/
// 思路
// dp三部曲
// 遇到障碍物怎么办  dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
var uniquePathsWithObstacles = function (obstacleGrid) {// 先得到m,nconst m = obstacleGrid.length;const n = obstacleGrid[0].length;// 1. 确定dp数组及下标dp = Array(m).fill().map((item) => Array(n).fill(0));//   2. dp递推公式// dp[i][j] = dp[i-1][j]+ dp[i][j-1]//   3. 初始化for (let i = 0; i < m && obstacleGrid[i][0] === 0; i++) {dp[i][0] = 1;}for (let j = 0; j < n && obstacleGrid[0][j] === 0; j++) {dp[0][j] = 1;}//   4. 遍历for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];
};

64.最小路径和

/*** @param {number[][]} grid* @return {number}*/
// 思路
// dp三部曲完成
// dp[j][j] 的含义是到达ij这个位置的最小和
var minPathSum = function (grid) {const m = grid.length;const n = grid[0].length;//   1. 确定dp数组及下标dp = Array(m).fill().map((item) => Array(n).fill(0));//  2. 确定递推公式//   dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]// 3. 初始化dp[0][0] = grid[0][0];for (let i = 1; i < m; i++) {dp[i][0] = grid[i][0] + dp[i - 1][0];}for (let j = 1; j < n; j++) {dp[0][j] = grid[0][j] + dp[0][j - 1];}//   4. 遍历for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}return dp[m - 1][n - 1];
};