leetcode Dynamic Programming

leetcode 174题

Posted by franki on August 31, 2021

leetcode 174题 地下城游戏

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

思路

动态规划

代码

/**
 * @param {number[][]} dungeon
 * @return {number}
 */
function calculateMinimumHP(dungeon) {
    if (dungeon.length === 0) {
        return 0;
    }
    const m = dungeon.length;
    const n = dungeon[0].length;
    const dp = new Array(m);
    for (let i=0; i<m; i++) {
        dp[i] = new Array(n);
    }
    dp[m-1][n-1] = Math.max(1-dungeon[m-1][n-1], 1);
    for (let i=n-2; i>=0; i--) {
        dp[m-1][i] = Math.max(1, dp[m-1][i+1]-dungeon[m-1][i]);
    }
    for (let i=m-2; i>=0; i--) {
        dp[i][n-1] = Math.max(1, dp[i+1][n-1]-dungeon[i][n-1]);
    }
    for (let i=m-2; i>=0; i--) {
        for (let j=n-2; j>=0; j--) {
            dp[i][j] = Math.min(Math.max(1, dp[i][j+1]-dungeon[i][j]), Math.max(1, dp[i+1][j]-dungeon[i][j]));
        }
    }
    return dp[0][0];
}

复杂度分析

  • 时间复杂度：O(N^2)
  • 空间复杂度：O(N^2)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS