动态规划是从初始值算到目标值。
递归是从目标值推到初始值。
1.Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
思想：数组的元素都是比target小的，用dp[i]表示组成i的所有组合的可能的个数。dp[target]=sum(dp[target-a[i]),比如dp[2]=dp[2-1]+dp[2-2]=dp[1]+dp[0]表示的意思就是组成1的所有可能的组合然后加上1 以及组成0的所有可能的组合加上2 即为组成2 的所有可能的组合。然后用填表法求出dp[]数组的每个值。
public int getCombinationSum(int[] a,int target){
if(target==0){
return 1;
}
int[] dp=new int[target+1];
dp[0]=1;
for(int i=1;i<=target;i++){
for(int j=0;j<a.length;j++){
if(i>=a[j]){
dp[i]=dp[i]+dp[i-a[j]];//第一个操作数dp[i]表示前面累计算到的结果
}
}
}
return dp[target];
}
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
思想：建立一个dp数组。dp[i]表示当凑齐i时最少要多少个数字组成。状态转移方程dp[i] = Math.min(dp[i-k] + 1,dp[i]);
解释一下吧，dp[i-k]只要不等于Integer.MAX_VALUE，证明凑齐i-k，有解。并且前面已经算出来了，这时候再加上k的1位数字就行。为了保证最少，所以要在诸多解中取最小值。
public int minNumberOfCoin(int[] a,int target){
int[] dp=new int[target+1];
//Arrays.fill(dp, target+1);?
for(int i=1;i<dp.length;i++){
dp[i]=Integer.MAX_VALUE;
}
dp[0]=0;
for(int i=1;i<=target;i++){
for(int j=0;j<a.length;j++){
if(i>=a[j]){
dp[i]=Math.min(dp[i], dp[i-a[j]]+1);
}
}
}
return dp[target]==target+1?-1:dp[target];
}
阅读数：259
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Note: You can assume that
0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into signed 32-bit integer
Example 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
Given a positive integer n, find the least number of perfect square numbers (for example,1, 4, 9, 16, ...) which sum to
n.
For example, given n = 12, return3 because
12 = 4 + 4 + 4; given n = 13, return2 because
13 = 4 + 9.
如果一个数x可以表示为一个任意数a加上一个平方数bｘb，也就是x=a+bｘb，那么能组成这个数x最少的平方数个数，就是能组成a最少的平方数个数加上1（因为bb已经是平方数了）
dp[0] = 0
dp[1] = dp[0]+1 = 1
dp[2] = dp[1]+1 = 2
dp[3] = dp[2]+1 = 3
dp[4] = Min{ dp[4-11]+1, dp[4-22]+1 }
= Min{ dp[3]+1, dp[0]+1 }
= 1
dp[5] = Min{ dp[5-11]+1, dp[5-22]+1 }
= Min{ dp[4]+1, dp[1]+1 }
= 2
dp[13] = Min{ dp[13-11]+1, dp[13-22]+1, dp[13-33]+1 }
= Min{ dp[12]+1, dp[9]+1, dp[4]+1 }
= 2
dp[n] = Min{ dp[n - ii] + 1 }, n - ii >=0 && i >= 1
/**
*
* n=a+b*b
* dp(n)=min(dp(n-b*b))+1
*/
public int minSquare(int n){
int[] dp=new int[n+1];
dp[0]=0;
for(int i=1;i<=n;i++){
dp[i]=Integer.MAX_VALUE;
for(int j=1;j*j<=i;j++){
dp[i]=Math.min(dp[i-j*j]+1, dp[i]);
}
}
return dp[n];
}
//Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right
//which minimizes the sum of all numbers along its path.
//Note: You can only move either down or right at any point in time.
//Example 1:
//[[1,3,1],
//[1,5,1],
//[4,2,1]]
//Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.
public int getMinPathCost(int grid[][]){
int[][] result=new int[grid.length][grid[0].length];
result[0][0]=grid[0][0];
for(int i=1;i<result[0].length;i++){
result[0][i]=result[0][i-1]+grid[0][i];
}
for(int j=1;j<result.length;j++){
result[j][0]=result[j-1][0]+grid[j][0];
}
for(int m=1;m<grid.length;m++){
for(int n=1;n<grid[0].length;n++){
result[m][n]=Math.min(result[m-1][n],result[m][n-1])+grid[m][n];
}
}
return result[grid.length-1][grid[0].length-1];
}
上面算法的时间复杂度是O（n*m）.如何用一维数组优化？
//There are a row of n houses, each house can be painted with one of the three colors: red, blue or green.
//The cost of painting each house with a certain color is different. You have to paint all the houses such
//that no two adjacent houses have the same color.
//The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example,
//costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1
//with color green, and so on... Find the minimum cost to paint all houses.
//Note:
//All costs are positive integers.
https://blog.csdn.net/u012175043/article/details/50050379
网友评论