动态规划

寻找岛屿

function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;

    let count = 0;

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === '1') {
                // 发现一个岛屿，进行深度优先搜索
                dfs(grid, i, j);
                count++;
            }
        }
    }

    return count;
}

function dfs(grid, i, j) {
    // 越界检查
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] === '0') {
        return;
    }

    // 将当前陆地标记为已访问（这里用'0'表示）
    grid[i][j] = '0';

    // 深度优先搜索上下左右四个方向
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

// 示例
const grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
];

console.log(numIslands(grid)); // 输出岛屿的数量

算法题：给定⼀个m×n⽹格，左上⻆起点标记为"Start" ，每次移动⼀步， 求⾛到Finish总共有多少条不同的路径？

//dp[i][j] = dp[i-1][j] + dp[i]
function uniquePaths(m, n) {
  const dp = Array(m).fill(0).map(() => Array(n).fill(0));

  // 初始化起始位置
  dp[0][0] = 1;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i > 0) {
        dp[i][j] += dp[i-1][j];
      }
      if (j > 0) {
        dp[i][j] += dp[i][j-1];
      }
    }
  }

  return dp[m-1][n-1];
}

// 测试示例
console.log(uniquePaths(3, 7)); 

221. 最大正方形

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

    const m = matrix.length;
    const n = matrix[0].length;
    let imax = 0;
    if( m === 0 || n ===0 ){
        return imax;
    }
    const dp = Array(m).fill(0).map(() => Array(n).fill(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
                }
                imax = Math.max(imax,dp[i][j])
            }
        }
    }

    return imax * imax;

120. 三角形最小路径和

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 示例 2：

输入：triangle = [[-10]] 输出：-10

解法1

从倒数第2层开始向上，每次从下一层中取出最小的那个，与当前值相加。

最顶端的值[0][0]，就是最短的路径！

/**
* @param {number[][]} triangle
* @return {number}
  */
  var minimumTotal = function(triangle) {
  const row = triangle.length;
  if (row === 0) {
  return row;
  }
  // 倒数第二层
  for (let i = row - 2; i >= 0; i--) {
  const size = triangle[i].length;
  for(let j=0;j<size;j++) {
  const min = Math.min(triangle[i+1][j],triangle[i+1][j+1])
  triangle[i][j]+=min;
  }
  }
  return triangle[0][0]
  };

象棋马走日字的方法数

function isValid(x, y) {
  return x >= 0 && x < 7 && y >= 0 && y < 7;
}

function knightMoves(x0, y0, xn, yn, n) {
  if (n === 0) return x0 === xn && y0 === yn ? 1 : 0;

  const moves = [
    [2, 1], [2, -1], [-2, 1], [-2, -1],
    [1, 2], [1, -2], [-1, 2], [-1, -2]
  ];

  let count = 0;
  for (const [dx, dy] of moves) {
    const newX = x0 + dx;
    const newY = y0 + dy;
    if (isValid(newX, newY)) {
      count += knightMoves(newX, newY, xn, yn, n - 1);
    }
  }
  return count;
}