森田賢二のleetCodeの使い方、解説、解答を毎日更新しているキャラクター

leetcodeでDPを学習するときのおすすめ 順番

leetcodeでDPを学習するときのおすすめ 順番

leetCodeどこからやっていいか分からない問題があるかと思います
私の場合ありました
特にDPはやっておきたいので闇雲にやっていましたが
ちゃんとその中でもカテゴリー分けしていると思うので
順番を決めたくなってきました
そこで調べた結果このようになりました

  1. 動的計画法の基礎

    • 練習問題: 70. Climbing Stairs, 509. Fibonacci Number, 1143. Longest Common Subsequence, 416. Partition Equal Subset Sum, 0/1 Knapsack
  2. 1次元配列を使ったDP

    • 練習問題: 198. House Robber, 300. Longest Increasing Subsequence, 62. Unique Paths, 53. Maximum Subarray
  3. 2次元配列を使ったDP

    • 練習問題: 64. Minimum Path Sum, 72. Edit Distance, 5. Longest Palindromic Substring, 221. Maximal Square
  4. 状態圧縮DP

    • 練習問題: 120. Triangle, 931. Minimum Falling Path Sum, 410. Split Array Largest Sum
  5. その他の応用DP

    • 練習問題: 312. Burst Balloons (区間DP), 935. Knight Dialer (個数DP), 847. Shortest Path Visiting All Nodes (グラフDP)

なお、これらはあくまで例であり、LeetCodeにはこれ以外にも多くのDP問題が存在します。