Dynamic Programming
問題 2分木が与えられる。ノードは数値を持っていて以下の条件で数値の和が最大の値を見つける問題。 条件 直接つながれている隣同士のノードは取る事ができない。 House Robber III - LeetCode 解き方 それぞれのノードについて、そのノードの値を和に含め…
問題 N個の整数を持つ配列が与えられる。隣接する要素は取れないという条件で、各要素の和の最大を求める問題。 例 [1, 2, 3, 4, 5] という配列の場合は以下のようなとり方がある 1 , 3, 5 → 9 1, 4 → 5 1, 5 → 6 2, 4 → 6 2, 5 → 7 max = 9 leetcode.com 解…
問題 Best Time to Buy and Sell Stock | LeetCode OJ ソースコード
問題 N枚の異なるコインと支払いたい金額moneyが与えれる。与えられたコインはそれぞれ無限に使える時、与えられたコインを使って合計金額がmoneyとなるような支払い方法の通り数を求める問題。 www.hackerrank.com 解法 動的計画法と用いることで計算量O(N*…
問題 始め階段の0段目にいて、N段目までの登り方の方法の数を求める問題。 階段は1段、2段又は3段を一気に登る事ができる。 www.hackerrank.com 解法 全列挙するためには、今いる段から1段登るか2段登るか3段登るかの3通りを毎回行うので、3N通り行…
問題 D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder N(1 <= N <= 50)個の品物が与えられ、それぞれの品物には価値Vi(1 <= i <= N)が設定されている。A個以上、B以下の品物を取ることが出来る時、選択した品物の価値の最大の平均値と、…
Problem Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6. leetcode.com…
Problem Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0, 0) to (X, Y)? How to Solve By using Dynam…
Problem A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. How to Solve This problem can be solved e…
Problem https://leetcode.com/problems/bomb-enemy/ How to Solve This problem can be solved by using Dynamic Programming. The point of this problem is that one spot in the grid can divide into four direction (up, down, left, right). We can c…