Scribd
Upload
3 views4 pages

DP Cheatsheet Java Printable

The document provides a cheat sheet for dynamic programming problems in Java, including solutions for Climbing Stairs, House Robber, and Coin Change. Each problem is accompanied by a problem statement, example, high-level approach, and Java solution. It also includes quick recognition tips for identifying dynamic programming problems and a golden rule for solving them.

Uploaded by

rtrbaba
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views4 pages

DP Cheatsheet Java Printable

The document provides a cheat sheet for dynamic programming problems in Java, including solutions for Climbing Stairs, House Robber, and Coin Change. Each problem is accompanied by a problem statement, example, high-level approach, and Java solution. It also includes quick recognition tips for identifying dynamic programming problems and a golden rule for solving them.

Uploaded by

rtrbaba
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Dynamic Programming Cheat Sheet (Java)

34. Climbing Stairs


Problem Statement
You are climbing a staircase. It takes n steps to reach the top. Each time you
can climb either 1 step or 2 steps. Return the number of distinct ways to
reach the top.

Example
Input: n = 3
Output: 3

Explanation:
1 + 1 + 1
1 + 2
2 + 1

High-Level Approach
 This is a classic DP problem because the current answer depends on
previous results.
 To reach step i, you can come from i-1 or i-2.
 Use a DP array to store the number of ways for each step.

Java Solution
public int climbStairs(int n) {
if (n <= 2) {
return n;
}

int[] dp = new int[n + 1];

dp[1] = 1;
dp[2] = 2;

for (int i = 3; i <= n; i++) {


dp[i] = dp[i - 1] + dp[i - 2];
}

return dp[n];
}
35. House Robber
Problem Statement
You are a robber planning to rob houses along a street. Each house has
some money, but adjacent houses cannot be robbed together. Return the
maximum amount of money you can rob.

Example
Input: nums = [2,7,9,3,1]
Output: 12

Explanation:
Rob house 1 (2), house 3 (9), and house 5 (1).
Total = 12

High-Level Approach
 For every house, we have two choices:
o Rob it and skip the previous house.
o Skip it.
 Use DP to store the maximum money possible up to each house.

Java Solution
public int rob(int[] nums) {
if ([Link] == 1) {
return nums[0];
}

int[] dp = new int[[Link]];

dp[0] = nums[0];
dp[1] = [Link](nums[0], nums[1]);

for (int i = 2; i < [Link]; i++) {


dp[i] = [Link](dp[i - 1], dp[i - 2] + nums[i]);
}

return dp[[Link] - 1];


}
36. Coin Change
Problem Statement
You are given coins of different denominations and an amount. Return the
fewest number of coins needed to make up that amount. If it is not possible,
return -1.

Example
Input: coins = [1,2,5], amount = 11
Output: 3

Explanation:
11 = 5 + 5 + 1

High-Level Approach
 Use DP where dp[i] stores the minimum coins needed for amount i.
 For each coin, try updating the minimum coins required.
 Build solutions from smaller amounts to larger amounts.

Java Solution
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];

[Link](dp, amount + 1);

dp[0] = 0;

for (int i = 1; i <= amount; i++) {

for (int coin : coins) {

if (coin <= i) {
dp[i] = [Link](dp[i], dp[i - coin] + 1);
}
}
}

return dp[amount] > amount ? -1 : dp[amount];


}
Quick DP Recognition Tips
Signal in Problem Likely DP
Count ways Climbing Stairs
Maximum profit/value House Robber
Minimum operations/coins Coin Change
Repeated overlapping Dynamic
calculations Programming

DP Golden Rule
1. Define DP state
2. Find recurrence relation
3. Identify base cases
4. Build bottom-up or top-down

You might also like