House Robber II The trick is to find the max value between robbing 0 to n-2 and 1 to n-1, so that we avoid the rounding issue.

# Tag: DP

Triangle. Surprisingly, this problem can be solved by the same method as in Pascal’s Triangle.

Distinct Subsequences. Classic DP problem. Define dp[i,j] is the number of distinct subsequences between s[0..j-1] and t[0..i-1]. (it is a bit tedious on the subscript) Then if s[j] == t[i]…

Decode Ways. I solve this problem by using DP with some careful case handling. Define DP[i] define the number of decoding ways end at position i. You can checkout the…

Minimum Path Sum. Still using the same DP traverse method as Unique Paths. But this time since we are finding the minimum path sum, so instead of sum two paths together,…

Unique Paths II. Same as Unique Paths. But DP[i,j] = 0 if position i,j are an obstacles.

Unique Paths. I solve this problem by using DP. Define DP[i,j] to be the number of paths from the start point to position i,j. The we know DP[i,j] = DP[i-1,j]…