跳到主要内容

动态规划

状态转移方程​

2 维 f(i, j) <== f(i+1, j-1)​

那么怎么在保证前面的状态已经算出来呢：

for (int right = 0; right < n; right++) {
    for (int left = right; left >= 0; left--) {
        memo[i][j] = ...
    }
}
  1. 最长回文子串 https://leetcode.cn/problems/longest-palindromic-substring/description/

f(i) <== f(i-1)​

  1. 跳跃游戏 https://leetcode.cn/problems/jump-game/description/
  2. 买卖股票的最佳时机 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
  3. 最大子数组和 https://leetcode.cn/problems/maximum-subarray/description/

f(i, j) <== f(i-1, j), f(i, j-1)​

  1. 不同路径 62. 不同路径

f(i) <== f(i-1), f(i-2)​

  1. 爬楼梯 https://leetcode.cn/problems/climbing-stairs/description/
  2. 打家劫舍 https://leetcode.cn/problems/house-robber/description/

f(i) <== f(i-c1), f(i-c2), ..., f(i-cn)​

c1, c2, ..., cn 为固定常数。跳台阶的进阶版。

  1. 零钱兑换 https://leetcode.cn/problems/coin-change/description/

f(i) <== f(0), f(1), ..., f(i-1)​

  1. 最长递增子序列 https://leetcode.cn/problems/longest-increasing-subsequence/description/